Problem overview
The method removeDuplicates receives an array of integers, nums, and must return an array in which every value appears once. The order may be anything. The statement asks for an in-place solution: no second array, only O(1) extra memory, and an O(n log n) running time.
In the example, [2, 3, 1, 1, 4, 3, -2, 1] holds five different values: 2, 3, 1, 4 and -2. Any ordering of those five numbers is a correct answer.
Approach: sort, then compact the array
Equal values are hard to find in an unsorted array, but easy in a sorted one: they sit next to each other. After sorting in ascending order, a value is new exactly when it differs from the element before it.
The first idea is to push each new value into a second array. That works, but it uses O(n) extra space. The in-place version uses the front of nums itself as the output. A write index p marks where the last distinct value was placed. Each time a new value appears, p moves one step and the value is copied there. The write position never passes the read position, so nothing unread gets overwritten.
Take the sorted array [-2, 1, 1, 1, 2, 3, 3, 4]. Index 0 holds -2 and stays. At index 1 the value 1 is new, so p becomes 1 and the array stays as is. At index 4 the value 2 is new, so p becomes 2 and nums[2] becomes 2, giving [-2, 1, 2, 1, 2, 3, 3, 4]. The value 3 at index 5 goes to position 3, and 4 at index 7 goes to position 4. The first five elements are now -2, 1, 2, 3, 4.
A Set would also remove duplicates in one line, [...new Set(nums)], and it keeps the first-seen order. It takes O(n) time but also O(n) extra space, so it breaks the in-place rule. Sorting trades some time for the space guarantee.
Why is it safe to overwrite? When a write happens, p is at most i, so it lands on the position being read or on one already read. Values that haven't been read yet are never touched.
Step by step
- Sort
numswith(a, b) => a - bso equal values become neighbours. The comparator keeps the sort numeric; without it, 10 would sort before 9. - Declare
pas 0. It is the index of the last distinct value placed. The first element is always kept, so it is already in place. - Loop from
i = 1over the rest of the array. - Check for a new value:
nums[i] !== nums[i - 1]. Because the array is sorted, a difference from the previous element means a first occurrence. - Move
pforward and copy:p++first, thennums[p] = nums[i]. The value lands right after the distinct values found so far. - Return the first
p + 1elements withslice(0, p + 1). Indexpis the last valid one, so the length isp + 1.
The solution in TypeScript
class Solution {
removeDuplicates(nums: number[]): number[] {
nums.sort((a, b) => a - b);
let p = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
p++;
nums[p] = nums[i];
}
}
return nums.slice(0, p + 1);
}
}
Details worth knowing:
- The array keeps its length. After the loop,
numsstill has its original length, with leftover values after positionp. In the example, the array ends as[-2, 1, 2, 3, 4, 3, 3, 4]. Only the firstp + 1elements are the answer. slicereturns a new array. The returned array is separate fromnums. It holds at mostnvalues, and it is the output, so the lesson doesn't count it as extra space. Settingnums.length = p + 1would truncate the array itself instead.!==. It compares without converting types, so it is the safe default in TypeScript. For numbers, it matches what!=would do here.- Sorting changes the order. The result is in ascending order, not in the order the values first appeared. The statement allows any order.
Complexity
Time: O(n log n). The sort takes O(n log n). The loop makes one pass with constant work per element. The final slice copies at most n values.
Space: O(1) besides the returned array. The compaction uses only p and i, and the sort works in place.
Edge cases and common mistakes
- An empty array. The loop doesn't run, and
slice(0, 1)of an empty array is empty, so the result is[]. - One element.
[5]stays[5]. - All values equal.
[7, 7, 7]gives[7], becausepnever moves. - Returning
slice(0, p). That drops the last distinct value, sincepis an index and not a count. - Copying before moving
p. Writingnums[p] = nums[i]beforep++overwrites the last distinct value instead of adding a new one. - Skipping the comparator. Without it, the array is ordered as strings. Equal numbers still stay together, but the result's order is surprising:
[10, 9, 9, 100]would come back as[10, 100, 9]. With the comparator it is[9, 10, 100].
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives[-2, 1, 2, 3, 4], which has the same values as the statement's example in a different order.[10, 9, 9, 100]gives[9, 10, 100].[7, 7, 7]gives[7].[]gives[].