How do you remove duplicates from a sorted array in place and return the new length?
SHORT ANSWER
Keep a write index. Because the array is sorted, a value is new only if it differs from the last value written. Copy it forward and advance the write index; the final write index is the new length.
Explain it simply
Think of a sorted attendance sheet where a student signed several times. Equal names sit next to each other, so you only need to compare each name with the last one you kept. If it is different, keep it; if not, skip it.
The slot at index 0 is always kept, so the write index starts at 1.
Example
js
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let write = 1;
for (let read = 1; read < nums.length; read++) {
if (nums[read] !== nums[write - 1]) {
nums[write] = nums[read];
write++;
}
}
return write;
}
const a = [1, 1, 2, 2, 2, 3];
const k = removeDuplicates(a);
console.log(k); // Output: 3
console.log(a.slice(0, k)); // Output: [1,2,3]Complexity
Time O(n), space O(1).
What to say in the interview
"The array is sorted, so duplicates are adjacent. I keep a write index and copy a value only when it differs from the last kept value. The first k elements are then unique, and I return k. Time is O(n) and space is O(1)."
Common mistakes
- Using splice inside a loop. Each splice shifts elements, so the whole thing becomes O(n squared).
- Forgetting that this trick relies on the array being sorted.