Given an array of integers, remove the duplicates in-place such that each unique element appears only once.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
The resulting array can be in any order.
Example:
Input: [2, 3, 1, 1, 4, 3, -2, 1] Output: [2, 3, 1, 4, -2]
Note:
Your algorithm should run in O(n log n) time and use O(1) extra space.
Hints:
Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another. Also, let's remove the O(1) extra space constraint for now to make the problem easier. Let's use an extra array
uniqueValues and add the unique values from nums there.
Then, we can traverse the sorted array
nums from left to right using an index i. We should add the element at index i into uniqueValues only if that value has not been seen before. How can we check this?
The element at index
i has never been seen before if it is different from the element at index i - 1.
It's time to solve the question with the original constraint. We will still traverse sorted
nums but each time we find a new unique element, we will overwrite an element of nums with this value, starting from the left:
- The first unique value will be stored at index
0ofnums - The second unique value will be stored at index
1 - ...
We will use an index variable
p, initially equal to 0, to keep track of the index where the last unique value was placed.
We will traverse
nums and check if the element at index i is different from the element at index i - 1. If so, we will increment p and then copy the element at index i to index p. What should we return when we finish the traversal?
We should return the first
p + 1 elements of nums.
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Solution #2 · O(n log n) / O(1)
Free plan: 30 tutor messages. PRO is unlimited.
Saved
Ctrl + Enter to check
