Problem Description

Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length.

Do not allocate extra space for another array; you must modify the input array in-place with O(1) extra memory.

Example 1:

Given numbers = [1, 1, 2],

The function should return length 2, with the first two elements of numbers being 1 and 2.

You don’t need to consider elements beyond the returned length.

Example 2:

Givan numbers = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4],

The function should return length 5, with the first five elements of numbers being 0, 1, 2, 3, 4.

You don’t need to consider elements beyond the returned length.

Analysis

Because the array is sorted, identical values are always adjacent. In languages like Java, arrays have no built‑in "delete" operation, so we must overwrite duplicate entries to compact the array.

Approach: Two Pointers

Use a slow pointer that marks the end of the compacted section (containing no duplicates), and a fast pointer that scans the remaining elements. Whenever a new distintc value is found, advance the slow pointer and overwrite the value at that position.

The first diagram below illustrates the initial state. The second and third diagrams show how the slow pointer moves and how elements are overwritten as the fast pointer scans.

Implementation (allowing at most one occurrence per value):

public static int compressSortedUnique(int[] data) {
    if (data == null) {
        return 0;
    }
    int totalLen = data.length;
    if (totalLen == 0) {
        return 0;
    }
    int writer = 0;
    // fast pointer can move up to the second-to-last element
    for (int reader = 0; reader < totalLen - 1; reader++) {
        if (data[reader] != data[reader + 1]) {
            writer++;
            data[writer] = data[reader + 1];
            System.out.println(Arrays.toString(data));
        }
    }
    return writer + 1; // length, not index
}

Extension: Allow at Most Two Occurrences

When the requirement changes to "each element may apppear at most twice", we can maintain a sliding window.

Concept:
writer - 2 and writer - 1 form a window where at most two duplicates exist. If the element at the fast pointer differs from the element at writer - 2, a "new" value has appeared and we can safely place it at writer because the constraint is already satisfied for the earlier part of the array.

public int compactWithMaxTwo(int[] sequence) {
    if (sequence.length < 3) {
        return sequence.length;
    }
    int anchor = 2;
    for (int cursor = 2; cursor < sequence.length; cursor++) {
        if (sequence[anchor - 2] != sequence[cursor]) {
            sequence[anchor] = sequence[cursor];
            anchor++;
        }
    }
    return anchor;
}

Generalization: Allow at Most K Occurrences

If the constraint is generalised to "at most k occurrences for each element", simply replace the 2 in the previous method with k.

public int compactWithMaxK(int[] values, int k) {
    if (values.length <= k) {
        return values.length;
    }
    int boundary = k;
    for (int idx = k; idx < values.length; idx++) {
        if (values[boundary - k] != values[idx]) {
            values[boundary] = values[idx];
            boundary++;
        }
    }
    return boundary;
}