Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. Return the number of unique elements k. The first k elements of nums must contain the unique elements in sorted order.

Example 1

Input: nums = [1,1,2] Output: k = 2, nums = [1,2,_]

Example 2

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

Constraints:

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

Solution: Slow/Fast Two Pointers
Complexity Analysis

Solution: Slow/Fast Two Pointers

slow marks the position to place the next unique element. fast scans through the array to find new unique values.

Start slow = 0, fast = 1.
Whenever nums[fast] != nums[slow], we found a new unique value: increment slow and copy it.
slow + 1 is the count of unique elements.

Java

public int removeDuplicates(int[] nums) {
    int slow = 0;

    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast]; // place next unique element
        }
        // else: duplicate — fast moves forward, slow stays
    }
    return slow + 1; // number of unique elements
}

Trace through Example 2: nums = [0,0,1,1,1,2,2,3,3,4]

fast	nums[fast]	nums[slow]	Action	slow
1	0	0	duplicate, skip	0
2	1	0	new → slow=1, nums[1]=1	1
3	1	1	duplicate, skip	1
4	1	1	duplicate, skip	1
5	2	1	new → slow=2, nums[2]=2	2
6	2	2	duplicate, skip	2
7	3	2	new → slow=3, nums[3]=3	3
8	3	3	duplicate, skip	3
9	4	3	new → slow=4, nums[4]=4	4

Return slow + 1 = 5. First 5 elements: [0,1,2,3,4].

Complexity Analysis

Time: O(n). Single pass through the array.
Space: O(1). in-place modification, no extra space.