AlgoMaster Logo

Remove Duplicates from Sorted Array

easyFrequency5 min readUpdated June 23, 2026

Understanding the Problem

Removing duplicates from an array is easy if we allow extra space: collect the distinct values somewhere else and copy them back. The in-place requirement is what gives this problem its shape. We must rearrange the original array so the unique elements occupy the front, then return how many there are. The contents past that point do not matter.

The array being sorted is the property we lean on. All copies of a value sit next to each other, so a value can only differ from the values seen so far if it differs from the element immediately before it. We never have to look further back than one position, which is what lets us solve this in a single forward pass.

Key Constraints:

  • 1 <= nums.length <= 3 * 10^4 → The array is never empty, so there is always at least one unique element. An O(n^2) scan would reach roughly 900 million comparisons at the upper bound, so we want O(n).
  • nums is sorted in non-decreasing order → Equal values are adjacent. Detecting a duplicate only requires comparing an element with its immediate predecessor, no hash set or counting array needed.

Approach 1: Using a Hash Set

Intuition

A hash set discards duplicates as you insert into it. Collect every value into a set, sort the distinct results (the output must stay in non-decreasing order), and write them back into the front of the array.

This ignores the fact that the input is already sorted and spends extra memory, so it is not the solution we will land on. It does establish a correct baseline to improve against.

Algorithm

  1. Insert all elements from nums into a hash set to get unique values.
  2. Convert the set to a list and sort it.
  3. Write the sorted unique values back into the first k positions of nums.
  4. Return k, the number of unique elements.

Example Walkthrough

Input:

0
0
1
0
2
1
3
1
4
1
5
2
6
2
7
3
8
3
9
4
nums

After collecting unique values into a set and sorting: {0, 1, 2, 3, 4}

Write them back into the first k positions of nums:

0
0
1
1
2
2
3
3
4
4
5
2
6
2
7
3
8
3
9
4
nums

Code

The next approach drops the extra set and the sort. Because duplicates are already adjacent in a sorted array, one forward pass that copies each new value to the front is enough, bringing the time down to O(n) and the space down to O(1).

Approach 2: Two Pointers (Optimal)

Intuition

Since the array is sorted, duplicates are always adjacent. There is no need for a hash set to detect them. Comparing each element with the last unique value already placed is enough.

Use two pointers over the same array. A write pointer insertPos marks where the next unique value belongs, and a read pointer i scans every element. The region before insertPos always holds the distinct values found so far, in order. When i lands on a value different from the one at insertPos - 1, it is a new unique value, so copy it to insertPos and advance the write pointer.

Algorithm

  1. If the array is empty, return 0.
  2. Initialize insertPos = 1 (the first element is always unique).
  3. Iterate through the array starting from index 1.
  4. When nums[i] is different from nums[insertPos - 1], place nums[i] at nums[insertPos] and increment insertPos.
  5. Return insertPos as the count of unique elements.

Example Walkthrough

1Initialize: insertPos=1, i=1. First element is always unique.
0
0
1
insertPos
0
i
2
1
3
1
4
1
5
2
6
2
7
3
8
3
9
4
1/9

Code