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.

Input: nums = [1,1,2]
Output: k = 2, nums = [1,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

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.

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].

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

Constraints:

Contents

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