Algorithm

Remove Duplicates

Two Pointer Pattern

Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums. Consider the number of unique elements of nums to be k. To get accepted, you need to do the following: Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums originally. The remaining elements of nums as well as the size of nums do not matter. Return k.

CONSTRAINTS
  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order
  • Solve in-place with O(1) extra memory
EXAMPLE 1
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Two distinct values (1 and 2), so k = 2 and the first two slots hold them. Anything left in slot 2 is ignored.
EXAMPLE 2
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Five distinct values (0,1,2,3,4), so k = 5 and they fill the first five slots in order. The rest is ignored.
EXAMPLE 3
Input: nums = [1]
Output: 1, nums = [1]
A single element is already distinct, so k = 1 and the array is unchanged.
What should I do with the remaining elements after the k unique ones?
It doesn't matter what you leave in array slots indices k and beyond. We only grade the first k elements.
Is the array guaranteed to be sorted?
Yes, it is sorted in non-decreasing order. You can rely on this.
Can I create a new array to store the unique elements?
No, you must do this in-place with O(1) extra memory.
What if the input array is empty?
The constraint is 1 <= nums.length, so you won't receive an empty array.

If we have a sorted list of items, we are fully guaranteed that identical numbers will always be sitting right next to each other. Our goal is to extract only the unique items, moving them to the front of the list.

The Shifting Penalty (O(N²))

The most obvious approach is to just delete a number whenever you see a duplicate. But behind the scenes, deleting an item from an array forces the computer to physically shift every single remaining item to the left to fill the gap. If we have to shift items for every duplicate, the process becomes incredibly slow.

python
for i in range(len(nums) - 1, 0, -1):
    if nums[i] == nums[i-1]:
        nums.pop(i) # Super slow! Shifts everything left.
The Two-Pointer Shortcut

To avoid deleting items and causing massive shifting, this is the perfect job for the Two-Pointer Pattern. This pattern is wildly important because it lets us compress the array "in-place", meaning we overwrite bad items instead of deleting them. We use two pointers moving from left to right:
- The Collector (Slow): Keeps track of where the next unique number should be saved.
- The Explorer (Fast): Runs ahead looking for completely new numbers.

Overwriting in Place

The Explorer checks every single number. It compares what it's currently looking at with the last unique number we collected. If they are exactly the same, it's a duplicate, so we just ignore it. But if it's different, the Explorer found a brand new number! We copy it into the Collector's spot and push the Collector forward.

python
if not nums: return 0

collector = 1
for explorer in range(1, len(nums)):
    if nums[explorer] != nums[collector - 1]:
        nums[collector] = nums[explorer]
        collector += 1

return collector
Worked Example:Remove Duplicates
0
1
1
1
colexp
2
2
3
2
4
3
We start with the first element '1' collected. Explorer starts at index 1 and sees a duplicate '1', so it does nothing.
0
1
1
2
2
2
colexp
3
2
4
3
Explorer finds 2 (different from the last unique value 1). We write 2 into index 1 and advance 'collector' to index 2.
0
1
1
2
2
2
col
3
2
exp
4
3
Explorer advances to index 3 and finds a duplicate 2, so it does nothing.
0
1
1
2
2
3
3
2
col
4
3
exp
Explorer finds 3 (different from the last unique value 2). We write 3 into index 2 and advance 'collector' to index 3.
Interactive Strategy Visualization

In-Place De-Duplication

Collector & Scout Pointers

GUARD
0
0
SCOUT
0
1
1
2
1
3
1
4
2
5
2
6
3
7
UNIQUE COUNT
1
SCANNED
1/8
The journey begins! Our 'Survivor Guard' (k) stands at index 0. Our 'Explorer Scout' (i) moves to index 1 and sees a 0. Since nums[i] (0) is the same as nums[k] (0), we skip it!

Key Insight

The Slow pointer acts as a gatekeeper, storing unique sorted elements. The Fast pointer scouts ahead. When a new value is found, we extend the unique sequence.

In-Place Efficiency

By modifying the array directly, we achieve O(1) space complexity. We overwrite duplicates with new unique values, so we don't need extra memory.

O(N²) Delete and Shift
→
O(N) Time · O(1) Space Write Pointer