RTE logo
← Back to DSA map
Two Pointers

Remove Duplicates from Sorted Array

Squeeze a sorted array so each value appears once, reusing the same array rather than building a new one.

Easy

Problem

Given an array sorted from smallest to largest, remove the repeats without making a new array, so each value appears only once. Return k, the count of different values. The first k slots must hold those values in their original order.

  • Do not create a new array.
  • Use O(1) extra space.
  • Keep the original order.

Examples

Input: nums = [1, 1, 2]
Output: k = 2, nums = [1, 2, _]
Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: k = 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Approach

Time O(n)Space O(1)
  1. The first element is always unique, so start with k = 1.
  2. Walk a reading position from index 1 to the end.
  3. If nums[read] differs from the last kept value nums[k - 1], copy it to nums[k] and increment k.
  4. Because the array is sorted, duplicates sit next to each other, so comparing with the last kept value is enough.

Common mistakes

  • Forgetting the empty array: return 0 before starting at k = 1.
  • The values after index k are left as they were, not removed - callers must read only the first k.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

REMOVE DUPES
Solution · JS
Array · read=— write=0
10
11
22
current —
prev unique —
k 0
unique prefix appears here
Read
—
Write
0
Current
—
Prev
—
k
0
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...