Remove Duplicates from Sorted Array — Write-Pointer Pattern

The Problem

You are given a sorted array nums. Remove the duplicates in place such that each unique element appears only once. The order of unique elements must be preserved. Return k, the number of unique elements, and the first k slots of nums must contain those unique elements. Anything beyond index k is don’t-care.

The dual nature of the return value — modifying the array and reporting a count — is what makes the problem mildly tricky. The judge checks both.

Intuition

The easy approach uses an auxiliary list to collect unique values and writes back. O(n) extra space, violating the in-place requirement.

The better way uses a write pointer k starting at 1. Walk through nums with a read pointer i from index 1 onward. Compare each element to nums[k - 1]. If they differ, the current element is new; write it to nums[k] and increment k. If they match, it is a duplicate and we skip.

Because the array is sorted, every duplicate of a value is contiguous, so comparing with the last written value is enough. If the array were not sorted, this algorithm would fail.

Explanation with Example

Take nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]. The unique values are [0, 1, 2, 3, 4], so k should be 5.

i:   1 2 3 4 5 6 7 8 9
val: 0 1 1 1 2 2 3 3 4
k:   1 2 2 2 3 3 4 4 5
                        ^
nums after pass: [0,1,2,3,4,2,3,3,4]
                ----------- k=5

The first 5 slots contain [0, 1, 2, 3, 4]. The slots beyond that are irrelevant per the problem statement.

Code

def removeDuplicates(nums):
    if not nums:
        return 0
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return k

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int k = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[k - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int k = 1;
        for (int i = 1; i < (int)nums.size(); ++i) {
            if (nums[i] != nums[k - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
};

Edge Cases

An empty input returns 0. A single-element array returns 1. An array with all identical values returns 1 and leaves the first slot as that value. A strictly increasing array returns n and the array is essentially unchanged.

If the array were not sorted, this algorithm would fail; the pattern depends on duplicates being contiguous.

Complexity Analysis

Time is O(n): one pass with constant work per element. Space is O(1): two integer pointers. Number of writes is at most n - 1, often much fewer when the array has long runs of duplicates.

The judge iterates through the first k positions to check correctness, so as long as those positions are right, anything past k is ignored.

How to Explain It in an Interview

Lead with the key observation: because the input is sorted, comparing each new element to the last accepted unique element is sufficient. Then describe the write pointer k as “the next position to place a new unique value” and walk through a small example like [1, 1, 2]. Finish by stating O(n) time and O(1) space.

If the interviewer asks about the variant allowing at most two duplicates, explain that you would compare against nums[k - 2] instead of nums[k - 1] and start k at 2. The pattern generalizes nicely.

Related Problems

• Remove Duplicates from Sorted Array II — at most two of each.
• Remove Element — remove a specific target.
• Move Zeroes — same write-pointer mechanic.
• Merge Sorted Array — pointers from the back.