Remove Duplicates from Sorted Array — Editorial

Opening the reading…

Intuitionthe sorted order separates values worth keeping from values worth skipping

Because nums is sorted, equal values sit next to each other. Once you have kept the first occurrence of a value, every later equal value can be ignored safely: no smaller or different value is hiding between them. This lets you scan from left to right without searching, shifting a block of elements, or revisiting an earlier position.

The first part of the array is the answer being built. Let k be the length of that part. The element at index k - 1 is the last unique value already written, so the current value is new exactly when nums[i] differs from nums[k - 1]. When it is new, write it at index k and advance k.

Approachread with i, write with k

Handle an empty array by returning 0, because there is no first unique value from which to initialize the write position.

Set k to 1 for a non-empty array, because the first element is always unique and already occupies the first output position.

Scan i from index 1 through the end of nums, because index 0 has already been kept and every later value must be classified.

Compare nums[i] with nums[k - 1], the last unique value written, because sorted order makes equality the exact test for a duplicate.

When the values differ, assign nums[k] = nums[i] and then increment k, because the new value belongs immediately after the existing unique prefix.

When the values are equal, do nothing and leave k unchanged, because the duplicate does not belong in the prefix and the next read should overwrite no valid result.

Return k, because it is both the number of unique values and the length of the prefix containing them; positions from k onward are irrelevant.

Complexityone scan and no auxiliary collection

MEASURE	BOUND	WHY
Time	O(n)	The read pointer examines each array element once. Each element causes at most one comparison and, if it is unique, one assignment, so the total number of operations grows linearly and no element is processed in a nested pass.
Space	O(1) extra space	The algorithm stores only the two integer indices and reuses nums for the compacted prefix. The returned prefix is required output and is excluded from auxiliary space; the bound stays O(1) for every input shape because the array is modified in place.

Here n is the length of nums.

Annotated solutionC++ · in-place two pointers

CPPCompacts each newly discovered value into the next position of the unique prefix.

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int k = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[k - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
};

The key placement is nums[k] = nums[i]. The read index i may be ahead of k because duplicates have been skipped, so this assignment overwrites values that no longer matter. It never damages an unanswered value: every future read occurs at an index i that is at least as far right as the current write position.

The comparison uses nums[k - 1] rather than nums[i - 1]. The previous input value may itself be a duplicate, while nums[k - 1] is guaranteed to be the last value retained in the result. The returned k is also why the algorithm does not need to clear the suffix; the problem declares every position from index k onward irrelevant.