Remove Duplicates from Sorted Array
Given an integer array sorted in non-decreasing order, remove duplicates in place so that each value appears once, keeping the relative order. Return the count k of unique elements; the first k slots must hold them.
- 1 ≤ n ≤ 3 · 10^4
- -100 ≤ nums[i] ≤ 100
- O(1) extra space
- Sorted, so duplicates are adjacent
- In-place with a *write* pointer and a *read* pointer
- Same-direction pointers
When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Keep a slow index w marking the end of the deduplicated prefix and a fast index r scanning the array. Whenever nums[r] differs from nums[w - 1] (the last kept value), copy it to nums[w] and increment w. Because the array is sorted, equal values are contiguous, so this single comparison identifies every duplicate.
- Building a new array from a set breaks the in-place requirement and ordering; for unsorted input a hash set is required.