26. Remove Duplicates from Sorted Array

Time: O(n)

Space: O(1)

Intuition

The array is sorted, so duplicates are adjacent. Use a slow pointer k that tracks where the next unique element should go. The fast pointer i scans ahead; whenever it finds a value different from the last accepted value, copy it to position k.

Algorithm

1If array is empty, return 0.
2Initialise k = 1 (first element is always unique).
3For i from 1 to n-1: if nums[i] != nums[i-1], set nums[k] = nums[i], k++.
4Return k.

Example Walkthrough

Input: nums = [1,1,2,3,3]

1.i=1: 1==1 skip. i=2: 2!=1 -> nums[1]=2, k=2.
2.i=3: 3!=2 -> nums[2]=3, k=3. i=4: 3==3 skip.
3.Array first 3 = [1,2,3].

Output: k = 3

Common Pitfalls

•Compare nums[i] with nums[i-1] (not nums[k-1]) - same result since the sorted property is preserved.
•Return k, not k-1; k is a count, not an index.

26.cs

// Approach: Two pointers — a slow write pointer k and a fast read pointer i.
// k starts at 1 (position of the next unique write slot).
// For each nums[i] from index 1 onward: if nums[i] != nums[i-1], write nums[i] to nums[k] and advance k.
// When the loop ends, the first k elements hold all unique values in sorted order.
// The constraint that the array is sorted means all duplicates are adjacent, enabling a single pass.
// Time: O(n) Space: O(1)

public class Solution
{
    public int RemoveDuplicates(int[] nums)
    {
        int i = 0;
        int j = i + 1;

        while (j < nums.Length)
        {
            if (nums[j] > nums[i])
            {
                i++;
                nums[i] = nums[j];
            }
            j++;
        }
        return i + 1;
    }
}

Was this solution helpful?