Remove Duplicates from Sorted Array
Remove duplicates from a sorted array in place with a read pointer and a write pointer, and return how many unique values remain.
Problem Understanding
Remove Duplicates from Sorted Array: given a sorted array, remove the duplicates in place so each value appears once, keep the original order, and return k, the number of unique values. Only the first k elements are checked.
Example: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] returns 5, with the array starting [0, 1, 2, 3, 4, ...].
The Intuition: Read Fast, Write Slow
Use two pointers moving in the same direction:
ireads every element.kmarks where the next unique value will be written;nums[0..k)is the answer so far.
Because the array is sorted, equal values sit together, so nums[i] is new exactly when it differs from the last value written, nums[k − 1]. New values are copied to nums[k]; duplicates are skipped. k only moves when something is written, so it never passes i, and nothing is overwritten before it is read. The same read/write idea drives Move Zeroes.
Interactive Walkthrough
The shaded prefix is nums[0..k), the unique values so far. i reads ahead; a duplicate is outlined red and skipped, and a new value is written at k, growing the prefix.
Dry Run Table
Input: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
| i | nums[i] | nums[k − 1] | Action | k |
|---|---|---|---|---|
| 1 | 0 | 0 | skip | 1 |
| 2 | 1 | 0 | write at 1 | 2 |
| 3, 4 | 1 | 1 | skip | 2 |
| 5 | 2 | 1 | write at 2 | 3 |
| 7 | 3 | 2 | write at 3 | 4 |
| 9 | 4 | 3 | write at 4 | 5 |
The Solution Template
Read with i, write unique values at k.
Remove Duplicates from Sorted Array Code
1var removeDuplicates = function(nums) {2 let k = 1;3 for (let i = 1; i < nums.length; i++) {4 if (nums[i] !== nums[k - 1]) nums[k++] = nums[i];5 }6 return k;7};
Edge Cases & Common Mistakes
- One element: the loop does not run; return 1.
- All the same: k stays 1.
- No duplicates: every value is written onto itself; k = n.
- Deleting from the array: removing elements shifts everything and costs O(n²); overwrite in place instead.
- Returning the array: the function returns k, the count, not a new array.
Summary
Keep the unique values in nums[0..k). Read every element with i; when it differs from nums[k − 1], write it at k and move k on. Return k. O(n) time, O(1) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet