[/dsa/leetcode]

26 - Remove Duplicates from Sorted Array

Wednesday, 16 September 2026

<easy> [problem]

A write pointer that trails a read pointer, comparing each candidate against the last element kept rather than against its neighbour.

{array}{two pointers}

Problem

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k. To get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important, as well as the size of nums.
  • Return k.
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order

Approach

A set solves this without any thought — build one from nums, copy it back, return its size. It is O(n log n) time and O(n) space.

Another approach would be two ponters. Split the array into a prefix that holds the answer and the untouched rest. i is the write pointer, the number of unique elements kept so far and therefore the next slot to write to. j is the read pointer, scanning for the next value worth keeping.

nums[0] is always unique, so both start at 1. For each j, compare nums[j] against nums[i - 1], the last element kept:

  • equal — a duplicate of something already in the prefix, so skip it with j++.
  • different — the first occurrence of a new value. Write it at nums[i] and advance both.

i only ever moves after a write, so it never overtakes j, and the prefix is overwritten only at positions already read. When j runs off the end, i is the count.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 1, j = 1;
        const int n = nums.size();
        while (j < n) {
            if (nums[j] == nums[i - 1]) {
                j++;
            } else {
                nums[i] = nums[j];
                j++;
                i++;
            }
        }
        return i;
    }
};
nums = [0, 0, 1, 1, 1, 2, 3]
i=1 j=1   0 == nums[0]=0   dup        -> j=2
i=1 j=2   1 != 0           write 1    -> [0,1,...]  i=2 j=3
i=2 j=3   1 == nums[1]=1   dup        -> j=4
i=2 j=4   1 == nums[1]=1   dup        -> j=5
i=2 j=5   2 != 1           write 2    -> [0,1,2,..] i=3 j=6
i=3 j=6   3 != 2           write 3    -> [0,1,2,3]  i=4 j=7
return 4
  • time: O(n) — each of j and i moves forward at most n times
  • space: O(1) — two indices, everything in place
quantinium © 2026