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
uniqueVals and push the unique values from nums there.
Then, we can traverse the sorted array
nums from left to right using an index i. We should push nums[i] into uniqueVals only if that value has not been seen before. How can we check this?
nums[i] has never been seen before if nums[i] != nums[i - 1].
It's time to solve the question with the original constriant. 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 in
nums[0] - The second unique value will be stored in
nums[1] - ...
We will use an index variable
p, initially equal to 0, to keep track of where we should place the next unique value we find.
We will traverse
nums and check if nums[i] != nums[i - 1]. If so, we will set nums[p] to nums[i] and increment p. What should we return when we finish the traversal?
We should return the subarray
nums[0...p].
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. Premium is unlimited.
Saved
Ctrl + Enter to check