Remove Duplicates from Sorted Array

Easy#26same direction

You get a non-empty array of numbers sorted in ascending order. Leave each number once at the start of the same array, in the same order, without a second array, and return how many there are. What lies after them does not matter. Our example: [1, 1, 2, 3, 3, 3, 5] → 4, with [1, 2, 3, 5] at the start.

26 Remove Duplicates from Sorted ArrayWalkthrough · 1×

Example: [1, 1, 2, 3, 3, 3, 5]. Both pointers walk right: read looks at every number, write marks where the next new one goes. A number is new when it differs from the last one written.

01112233435365write
unique, in placebeing readjust written hererepeats and leftoversnot read yet

nums[0] = 1 is the first number, so it is new: it stays, and the next new number goes to index 1

01/21
restart · back · play · step
Speed
1function removeDuplicates(nums):
2 write = 1
3 for read from 1 to len(nums) - 1:
4 if nums[read] != nums[write - 1]:
5 nums[write] = nums[read]
6 write = write + 1
7 return write
state
write
1
read
–
nums[read]
–
nums[write - 1]
1
nums
[1, 1, 2, 3, 3, 3, 5]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The array is sorted, so equal numbers stand next to each other. A repeat can only follow its own number, so comparing with the last number written is enough: no need to look further back.
  2. Left of write lies each number met so far, once and in ascending order. A new number is larger than all of them, so it goes right after them, at nums[write].
  3. When a number is written, write is never to the right of read, so a write only covers a cell that has already been read. No number still to be read is lost.

Complexity

Time O(n): read passes the array once, and each step does one comparison and at most one write. Memory O(1): two indices, and the numbers are rewritten inside the same array.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.