Remove Duplicates from Sorted Array
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
In a sorted list, remove duplicates in place so each value appears once, and report how many unique values remain.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Because the list is sorted, where are the duplicates of a value?
- Hint 2Keep a write position; a value is new if it differs from the last written one.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A photo album sorted by date has the same photo printed three times back to back. You flip through and move into a fresh album only the photos that differ from the last one you kept. The copies sit right next to each other, so you never have to search the whole album.
- The obvious way
Put the values in a set and rebuild: uses extra memory and ignores the in-place rule.
- The key insight
Equal values are neighbours, so a value is new exactly when it differs from the last one you kept. Copy each new value to the next write slot and move on; the first few slots end up holding the unique values in order.
- The algorithm
- Keep the first value. The write slot is the second position.
- Look at each next value. Same as the last kept one? Skip it.
- Different? Copy it into the write slot and move the write slot on.
- The write slot position is the count of unique values.
Watch it run
Examplenumbers = [0, 0, 1, 1, 2]
Keep the first 0. Count of unique so far = 1.
kept: [0]
Where people slip
- Compare with the last KEPT value (write - 1), not the previous position; this also adapts easily to "allow two copies".
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def remove_duplicates(nums):
if not nums:
return 0
write = 1 # next slot for a new value
for position in range(1, len(nums)):
if nums[position] != nums[write - 1]: # differs from the last kept
nums[write] = nums[position]
write += 1
return writeNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.