#35

Remove Duplicates from Sorted Array

easy

arraytwo-pointers

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place so that each distinct value appears only once. The relative order of the kept elements must stay the same.

Because the array can't be resized in place, you don't delete anything — instead you compact the unique values into the front of nums. Let k be the number of distinct values. Your job:

- Place the first k distinct values, in order, in nums[0] through nums[k - 1]. - Return `k`. Whatever ends up beyond index k - 1 doesn't matter.

Both the value you return and the first k elements of the mutated array are checked; the tail is ignored. Aim for O(n) time and O(1) extra space.

Example

Input: nums = [1,1,2]

Output: [1,2]

Distinct values are 1 and 2, so k = 2 and nums starts with [1, 2].

Constraints

0 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Intuition

The most direct approach leans on a Set: feed every value through it to drop repeats, then copy the distinct values back into the front of nums and return how many there were. A Set preserves first-seen order, so the sorted ordering survives.

function removeDuplicates(nums) {
  // A Set drops duplicates while keeping first-seen (sorted) order.
  const unique = [...new Set(nums)];
  // Write the distinct values back into the front of nums.
  for (let i = 0; i < unique.length; i++) nums[i] = unique[i];
  return unique.length; // the new logical length, k
}

Brute force — collect uniques in a Set, copy back: O(n) time, O(n) extra space.

This is O(n) time, but the Set is a whole second copy of the data — O(n) extra space on a problem that asks for O(1). Can we do better?

The key observation: the array is already sorted, so equal values are always adjacent. We never need a Set to spot a duplicate — a value is new exactly when it differs from the one right before it. That means we can compact in place with two same-direction pointers walking the array: a slow write pointer marking the end of the unique prefix, and a fast read pointer scanning ahead for the next new value. This same-direction slow/fast pairing is the Two pointers pattern.

Seed slow at index 0 (the first element is always kept). Each time fast lands on a value different from nums[slow], advance slow and write that value there. The unique count is slow + 1.

Walking it through:

nums = [0, 0, 1, 1, 2] · highlighted = unique prefix

slow↓

fast↓

nums[fast] 0 == nums[slow] 0 → fast++

A duplicate of the kept value — skip it, slow stays put.

slow↓

fast↓

nums[fast] 1 ≠ last kept 0 → ++slow, write nums[slow] = 1

A new value: advance slow and write it, extending the unique prefix to [0, 1].

slow↓

fast↓

nums[fast] 1 == nums[slow] 1 → fast++

Another duplicate, this time of the 1 we just kept — skip again.

slow↓

fast↓

nums[fast] 2 ≠ last kept 1 → ++slow, write nums[slow] = 2

Last new value written. fast falls off the end next.

slow↓

fast past end → return slow + 1 = 3

Prefix [0, 1, 2] holds the distinct values; k = 3.

Optimization

Two pointers

Keep a write pointer k at the position for the next distinct value (it also equals the count so far). Scan with a read pointer i: whenever nums[i] differs from the last value written (nums[k - 1]), write it at nums[k] and advance k. The first element is always distinct, so seed k = 1 when the array is non-empty. Return k.

O(n) time, O(1) extra space.

function removeDuplicates(nums) {
  // No elements means no distinct values: k = 0.
  if (nums.length === 0) return 0;
  // k is the write position AND the count so far; the first element is always kept.
  let k = 1;
  // i is the read pointer scanning ahead for the next new value.
  for (let i = 1; i < nums.length; i++) {
    // Sorted input keeps duplicates adjacent, so a value is new only when it
    // differs from the last one we kept (nums[k - 1]).
    if (nums[i] !== nums[k - 1]) {
      nums[k] = nums[i]; // compact the new value into the unique prefix
      k++;               // and grow the prefix
    }
  }
  return k; // number of distinct values, now sitting in nums[0..k-1]
}

Complexity analysis

Time complexity: O(n). Here's why:

The fast read pointer makes a single left-to-right pass over the array, visiting each element once.
Each step is O(1): one comparison against the last kept value, and at most one write plus a pointer bump.

There is no nesting and no second pass, so the overall time is O(n), where n is the length of nums.

Space complexity: O(1). Here's why:

The compaction happens in place — distinct values are written back into the front of the same array.
The only extra storage is the two index variables, the slow write pointer and the fast read pointer.

Nothing grows with the input — no Set, no copy — so the extra space is constant, O(1). (The Set-based brute force builds a whole second array of the uniques, which is O(n).)

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = []	[]	Empty array — no values, so k = 0 and the prefix is empty.
nums = [9]	[9]	Single element — already unique, kept as the only distinct value.
nums = [1,2,3,4]	[1,2,3,4]	No duplicates — every element is new, so the prefix is unchanged.
nums = [4,4,4,4]	[4]	All equal — every later value is a duplicate of the first, leaving one.
nums = [-3,-3,-1,-1,-1,6]	[-3,-1,6]	Repeated runs of varying length collapse to one each.
nums = [2,2,5,8,8]	[2,5,8]	Duplicates at both ends with a unique value between them.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor