Remove Duplicates from Sorted Array

Problem

Database engines frequently compact sorted log files by removing duplicate entries in-place before writing to storage. Given an integer array sorted in non-decreasing order, remove the duplicates in-place and return the number of unique elements. The judge reads the first k elements of the modified array.

Input: [1, 1, 2]                    → 2  (array becomes [1, 2, ...])
Input: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] → 5  (array becomes [0, 1, 2, 3, 4, ...])

Solution

Approach: same-direction slow/fast pointers for in-place compaction.

slow_index marks the position of the last unique value written so far, and fast_index scans every later element looking for the next distinct one. Because the array is sorted, every run of equal values is contiguous, so a simple nums[fast_index] != nums[slow_index] test is enough to detect a new value - there is no need to remember more than the last kept element. When fast finds a value different from the one at slow, advance slow first to open the next write slot, then copy the new value there. The invariant is that nums[0..slow_index] always holds the unique elements seen so far in order, so the compacted result grows one slot at a time at the front of the array.

Trace [1, 1, 2]: slow=0 (value 1). fast=1 sees 1, equal, skip. fast=2 sees 2, different - slow becomes 1, write nums[1]=2. The array front is now [1, 2] and the loop returns slow + 1 = 2.

Edge cases: the leading if not nums guard returns 0 for an empty array; a single element or an all-equal array never triggers a write and correctly returns 1, since slow_index stays at 0.

Complexity: O(n) time, O(1) space - fast makes one pass and writes happen in place with no second array.