Remove Duplicates from Sorted Array: Slow/Fast Pointer In Place

• Same-direction two pointers – a slow pointer k marks where the next unique value should be written; a fast pointer i scans every element.
• Copy-on-new rule – when a[i] != a[k], increment k and copy a[i] to a[k].
• Return value – k + 1 is the count of unique elements; the first k + 1 slots hold them in sorted order.
• O(n) time, O(1) space – one pass through the array with only an index variable as extra state.
• Sorted precondition – duplicates must be contiguous for the comparison to catch every group.

What is the Remove Duplicates from Sorted Array problem?

Given a sorted array, remove the duplicates in place so that each element appears only once. Return the new length. The first that-many elements of the array should hold the unique values in order. You must do this with O(1) extra memory.

At the National Bank of India, nightly ledger imports can produce duplicate transaction IDs because of retry logic. Rajesh must deduplicate the sorted ID list before posting.

How do the slow and fast pointers work?

Because the array is sorted, every group of duplicates is contiguous. You only ever compare the current element with the last one you decided to keep.

• k (slow) starts at index 0. The first element is always unique.
• i (fast) starts at index 1 and scans forward.
• If a[i] != a[k], this is a new unique value: advance k and copy a[k] = a[i].

Array: [1, 1, 2, 2, 3, 4, 4]

i=1: a[1]=1 == a[k=0]=1 → skip
i=2: a[2]=2 != a[k=0]=1 → k=1, a[1]=2
i=3: a[3]=2 == a[k=1]=2 → skip
i=4: a[4]=3 != a[k=1]=2 → k=2, a[2]=3
i=5: a[5]=4 != a[k=2]=3 → k=3, a[3]=4
i=6: a[6]=4 == a[k=3]=4 → skip

Result: [1, 2, 3, 4, ...], return k+1 = 4

How do you implement it? (with code)

package com.bank.batch;

import java.util.Arrays;

public class RemoveDuplicatesSorted {

    public static int removeDuplicates(int[] txnIds) {
        if (txnIds.length == 0) return 0;

        int k = 0;  // slow pointer: last unique position
        for (int i = 1; i < txnIds.length; i++) {
            if (txnIds[i] != txnIds[k]) {
                k++;
                txnIds[k] = txnIds[i];
            }
        }
        return k + 1;
    }

    public static void main(String[] args) {
        int[] ids = {1001, 1001, 1002, 1003, 1003, 1003, 1004};
        int uniqueCount = removeDuplicates(ids);
        System.out.println("Unique count: " + uniqueCount);
        System.out.println("Unique IDs: "
            + Arrays.toString(Arrays.copyOf(ids, uniqueCount)));
    }
}

Unique count: 4
Unique IDs: [1001, 1002, 1003, 1004]

Why compare against a[k] and not a[i-1]?

In the classic "keep one copy" version, both work because the kept region is a prefix of the unique values. But if the variant allows at most two copies, you compare against a[k-1] to check the count. Anchoring on the slow pointer region is the cleaner mental model that generalizes.

// Allow at most 2 copies: compare against a[k-1]
public static int removeDuplicatesAllowTwo(int[] a) {
    if (a.length <= 2) return a.length;
    int k = 1;
    for (int i = 2; i < a.length; i++) {
        if (a[i] != a[k - 1]) {
            k++;
            a[k] = a[i];
        }
    }
    return k + 1;
}

What happens on unsorted data?

On unsorted data, duplicates are not adjacent. The comparison a[i] != a[k] would miss scattered duplicates. You would need a HashSet to track seen values, costing O(n) extra memory.

// Unsorted: need a set
Set<Integer> seen = new HashSet<>();
int k = 0;
for (int i = 0; i < a.length; i++) {
    if (seen.add(a[i])) {
        a[k++] = a[i];
    }
}

What are the edge cases?

• Empty array – return 0.
• Single element – already unique; return 1.
• All elements the same – k stays at 0; return 1.
• All elements unique – every element is copied in place; return the original length.
• Two elements, same – return 1. Two elements, different – return 2.

What about Java array limitations?

Java arrays cannot shrink. The method does not physically remove anything; it returns the logical length and the caller must treat only that prefix as valid. In production, Rajesh would copy the prefix into a right-sized collection before handing it to downstream systems.

// Copy to right-sized array
int newLen = removeDuplicates(ids);
int[] unique = Arrays.copyOf(ids, newLen);

How is this different from removing a specific value?

| Problem | Comparison | Write rule |
|---|---|---|
| Remove duplicates (sorted) | a[i] != a[k] | Copy new unique to k |
| Remove specific value | a[i] != val | Copy non-matching to k |
| Allow at most 2 copies | a[i] != a[k-1] | Copy if under the limit |

All three use the same slow/fast pointer pattern but differ in the comparison condition.

What are common interview follow-up questions?

• Can you do it in O(1) space? – Yes, the slow/fast pointer uses constant extra space.
• What about at most K copies? – Compare against a[k - (K-1)].
• What if the array is unsorted? – Use a HashSet at O(n) space cost.
• What happens to elements after the new length? – They are garbage; the caller ignores them.