Remove Duplicates from Sorted Array II

Medium#80same direction

You get an array of numbers sorted from smallest to largest. Rewrite it in place so that every number appears at most twice, keeping the order, and return how many numbers are left; whatever lies after them does not matter. Our example: [1, 1, 1, 2, 2, 3, 3, 3, 3] → 6, and the array starts with [1, 1, 2, 2, 3, 3].

80 Remove Duplicates from Sorted Array IIWalkthrough · 1×

Example: [1, 1, 1, 2, 2, 3, 3, 3, 3]. read visits every number, write marks where the next kept one goes. A number is kept when it differs from nums[write - 2].

011121324253637383write
kept: the answer so farnums[read] and the nums[write - 2] it is compared withjust copied hereskipped or leftovernot read yet

write = 0: nothing is kept yet

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

← → step · space play/pause

Why it works

  1. Everything left of write is the answer so far, and it is sorted. If nums[read] equals nums[write - 2], it equals everything between them too, so the answer already ends with two copies of it, and a third is one too many.
  2. The neighbour is not enough: equal neighbours only say that the number repeats, not how many copies are already kept. In 1, 1, 1 the second and the third 1 look the same next to their neighbours, yet only the third must go. nums[write - 2] counts for us.
  3. At most k times: keep the first k numbers and compare with nums[write - k]. With k = 1 this is problem 26, Remove Duplicates from Sorted Array.

Complexity

Time O(n): read passes the array once, and each step is one comparison and at most one copy. Memory O(1): the array is rewritten in place, with only two indices on the side.

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.