Problem

Remove Duplicates from Sorted Array

LeetCode #26Easy
One write index, no extra array

Given a sorted integer array, remove the duplicates in place so each value appears once, keeping the relative order. Return k, the number of distinct values; the first k slots of the array must hold them.

Asked atAmazonMicrosoftAdobe
1
1
2
2
2
3
4
4
[0][1][2][3][4][5][6][7]
unique[]
Brute force · second array
▸
1unique ← []
2for x in arr:
3    if unique is empty or unique.last ≠ x: unique.append(x)
4return unique.length
state
  • extra spaceO(n)

line 1Build a fresh array and copy over anything we have not already copied.

Remove Duplicates from Sorted Array, animated walkthrough (Array sheet)