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.

Example 1:

Input: [4, 4, 9]
Output: 2
Explanation: the array becomes [4, 9, ...] and the judge reads the first 2 elements.

Example 2:

Input: [2, 2, 5, 5, 5, 8, 8, 11, 11, 14]
Output: 5
Explanation: the array becomes [2, 5, 8, 11, 14, ...] and the judge reads the first 5 elements.

Constraints:

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

Solution Breakdown

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 [4, 4, 9]: slow=0 (value 4). fast=1 sees 4, equal, skip. fast=2 sees 9, different - slow becomes 1, write nums[1]=9. The array front is now [4, 9] 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.