Remove duplicates: definition
Keep one occurrence of each distinct value in a sorted array. This is an example problem for the two-pointer technique: read scans the input while write marks the next free position in the answer.
Task example: Remove Duplicates from Sorted Array
Given integers sorted in non-decreasing order, update the original array so its first k positions contain the distinct values in order. Return k, the number of distinct values. Values after that prefix are ignored; the array does not need to shrink.
The underscores mean ignored positions, not values written by the algorithm. The demos also accept an empty array and return 0.
Collect & copy back: video explanation
nums = [1, 1, 2, 2, 3] · k = 3 · nums[:k] = [1, 2, 3]
Prefer reading? Follow the steps below.
- Create an empty list called unique. Read the sorted input from left to right. Keep a value only when the list is empty or it differs from the last value kept.
- For [1, 1, 2, 2, 3], keep the first 1, skip the repeated 1, keep 2, skip the repeated 2, and keep 3. The separate list becomes [1, 2, 3].
- Copy these values back into the first positions of nums. Return the list length: k = 3. The remaining positions do not matter.
Time complexity · O(n)
Scanning the input and copying at most n distinct values back both take linear time. Time complexity is O(n).
Space complexity · O(n)
The separate list can contain n values. Space complexity is O(n), so this baseline uses extra storage rather than meeting the constant-space in-place goal.
Two pointers: video explanation
nums = [1, 1, 2, 2, 3] · k = 3 · nums[:k] = [1, 2, 3]
Prefer reading? Follow the steps below.
- If the array is empty, return 0. Otherwise keep its first value and set write = 1, the next free position in the distinct prefix.
- Move read from index 1 to the end. Compare nums[read] with nums[write - 1], the last distinct value kept. Equal means a duplicate: move read on without changing write.
- When the values differ, write nums[read] into nums[write], then increment write. After the scan, return write as k.
- In the example, skip the second 1, write 2 at index 1, skip the repeated 2, then write 3 at index 2. Return k = 3 with prefix [1, 2, 3].
Why it works: sorted order puts duplicates next to each other. The prefix stores exactly the distinct values seen so far. write never goes ahead of read, so copying cannot destroy unread input.
Time complexity · O(n)
read visits each remaining position once. Each comparison and write takes constant time, so time complexity is O(n).
Space complexity · O(1)
Only two indices are stored; no separate list is created. Space complexity is O(1). Compared with collect & copy back, time stays O(n) while extra space drops from O(n) to O(1).