Remove Duplicates from Sorted Array

time O(n)space O(1)

The key insight: use a slow pointer to mark the position of the last unique element written, and a fast pointer to scan through the array. Since the array is sorted, duplicates appear consecutively. When nums[fast] != nums[slow], we've found a new unique element: advance slow and write nums[fast] there. All elements beyond slow are irrelevant after the process completes.

Details

Animated on: Given nums = [1, 1, 2, 2, 3], remove duplicates in-place such that the first k elements are unique. Return k = 3, and the first 3 elements become [1, 2, 3].

Problem:Remove Duplicates from Sorted ArrayEasy

Two Pointers

step 1 / 6

[0]

[1]

[2]

[3]

[4]

slow = 0, fast = 1: initialize the slow pointer at the first element (it's always unique so far) and fast at the second element; we're scanning to find the next unique value.

slow=0· arr[0] = 1
fast=1· arr[1] = 1

Pseudocode

1FUNCTION removeDuplicates(nums):
2  IF n = 0: RETURN 0
3  slow = 0
4  FOR fast from 1 to n-1:
5    IF nums[fast] != nums[slow]:
6      slow = slow + 1
7      nums[slow] = nums[fast]

← / → step · space play · Home restart

Every step in words

Show all 6 steps

slow = 0, fast = 1: initialize the slow pointer at the first element (it's always unique so far) and fast at the second element; we're scanning to find the next unique value.
fast = 1: nums[fast] = 1 nums[slow] = 1, they are equal, so this is a duplicate. Do nothing; just advance fast to 2.
fast = 2: nums[fast] = 2 nums[slow] = 1, they are different, so this is a new unique element. Advance slow to 1 and write nums[fast] = 2 at nums[slow]; array becomes [1, 2, 2, 2, 3].
fast = 3: nums[fast] = 2 nums[slow] = 2, they are equal, so this is a duplicate. Do nothing; just advance fast to 4.
fast = 4: nums[fast] = 3 nums[slow] = 2, they are different, so this is a new unique element. Advance slow to 2 and write nums[fast] = 3 at nums[slow]; array becomes [1, 2, 3, 2, 3].
fast = 5: loop terminates since fast >= n. The first k = slow + 1 = 3 elements are [1, 2, 3]; the remaining elements are irrelevant. Return k = 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Remove Duplicates from Sorted Array in the editor All Two Pointers problems Back to roadmap