Two Pointers crash course ↗ · 161

26. Remove Duplicates from Sorted Array

The array is already sorted, so duplicates sit next to each other. A slow / fast pointer pair compacts the uniques to the front in place: slow marks where the next unique value goes, fast scans for it. Return the new length k.

● EasyTwo PointersIn-place WriteTypeScript

PROBLEM What we're solving

Compact a sorted array so each value appears once, doing it in place, and return the count k of uniques. nums = [0,0,1,1,1,2,2,3,3,4] → k = 5 with nums[:5] = [0,1,2,3,4]. The tail beyond kis don't-care.

KEY IDEA Sorted ⇒ duplicates are adjacent

Insight → because the array is sorted, every run of equal values is contiguous. So a value is "new" exactly when it differs from the last unique we kept. Keep a slow write head at the end of the unique prefix; whenever fast finds a value != nums[slow], bump slow and copy it forward. No extra array, no set.

RECIPE Slow writes, fast scans

  • 0 · Edge case. Empty array ⇒ return 0.
  • 1 · Seed slow = 0. nums[0] is always the first unique, so the prefix already has one element.
  • 2 · Scan fast from 1. Compare nums[fast] to nums[slow] — the last value we kept.
  • 3 · On a new value, increment slow then set nums[slow] = nums[fast]. Duplicates are simply skipped.
  • 4 · Return slow + 1 — the length of the unique prefix.
Classic confusion → compare nums[fast] against nums[slow] (the last kept value), NOT against nums[fast - 1]. With this exact write order they happen to coincide here, but anchoring on slowis the version that generalizes (e.g. "allow each value at most twice"). Also remember to slow++ before writing, never after.

COST Complexity & alternatives

Set + new array
O(n) space
Easy, but allocates and isn't in place.
Two pointers
O(1) space
Single pass, O(n) time, zero extra memory.

Why it's optimal

You must read every element at least once, so O(n) time is unavoidable. The slow/fast trick does it with a constant number of extra variables — no set, no copy — which is the whole point of the "in place" requirement.

Pattern transfer → the slow/fast in-place compaction reappears in Remove Element, Move Zeroes, Remove Duplicates II(allow two), and any "filter in place keeping order" task. slow is always the write head; fast is the reader.

RUN IT Slow writes uniques, fast scans ahead

step 0 / 10
STARTSeed slow = 0: nums[0] is always the first unique value. Scan with fast from index 1.
1function removeDuplicates(nums: number[]): number {
2  if (nums.length === 0) return 0;
3▶  let slow = 0;                       // last write position of a unique value
4▶  for (let fast = 1; fast < nums.length; fast++) {
5    if (nums[fast] !== nums[slow]) {  // found a new value
6      slow++;                         // advance the write head
7      nums[slow] = nums[fast];        // write it forward
8    }
9  }
10  return slow + 1;                    // count of unique values = k
11}
nums00011213142526373849
State
0
slow
1
fast
1
k
slow (write head)fast (scanning)just wroteunique prefix
slowfast

TYPESCRIPT The solution, annotated

removeDuplicates.ts
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  let slow = 0;                       // last write position of a unique value
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {  // found a new value
      slow++;                         // advance the write head
      nums[slow] = nums[fast];        // write it forward
    }
  }
  return slow + 1;                    // count of unique values = k
}

Reading it block by block

Line 2 — empty guard. No elements means zero uniques; return 0 before touching any index.
Line 3 — seed the write head. nums[0] is automatically unique, so slow starts at 0: the unique prefix already contains one value.
Lines 4–5 — scan and compare. fast walks from 1. We compare against nums[slow], the last value we decided to keep. Equal ⇒ duplicate ⇒ do nothing.
Lines 6–7 — keep a new value. When nums[fast] differs, advance slow first, then copy nums[fast] into the freed slot. The prefix nums[0..slow] stays strictly increasing.
Line 10 — return the length. slow is the index of the last unique, so slow + 1 is the count k. The grader reads only nums[0..k-1].
Complexity → O(n) time — one pass, each element read once. O(1) extra space — only slow and fast, mutating the input array in place.

INTERVIEWFollow-ups they'll ask

  • "Allow each value at most twice?" (LC 80) Compare nums[fast] against nums[slow - 1] and start slow at 2 — the same write-head idea with a window of two.
  • "Array isn't sorted?"Then duplicates aren't adjacent; sort first (O(n log n)) or use a hash set (O(n) space). The two-pointer trick relies on sortedness.
  • "Why slow++ before the write?" The slot at slow already holds a kept value; the next unique belongs at slow + 1.
  • "Do we have to clear the tail?" No — the problem says elements beyond kare don't-care, so leaving the stale values is fine.

OPTIMAL Two Pointers

removeDuplicates.ts
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  let slow = 0;                       // last write position of a unique value
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {  // found a new value
      slow++;                         // advance the write head
      nums[slow] = nums[fast];        // write it forward
    }
  }
  return slow + 1;                    // count of unique values = k
}
Complexity → O(n) time — one pass, each element read once. O(1) extra space — only slow and fast, mutating the input array in place.

ALT 1 Hash set + rebuild (not in place)

O(n) time · O(n) space

Ignore the sortedness, dedupe with a Set, then copy unique values back. Works on unsorted input too, but allocates O(n) memory and violates the in-place spirit.

approach-2.ts
function removeDuplicates(nums: number[]): number {
  const seen = new Set<number>();
  let k = 0;
  for (const x of nums) {
    if (!seen.has(x)) {
      seen.add(x);
      nums[k++] = x;
    }
  }
  return k;
}
Note → Correct and order-preserving, but the set costs O(n) extra space for no benefit when the array is already sorted — the two-pointer version achieves O(1) space by comparing neighbors.

MNEMONIC The one-liner

"slow keeps, fast seeks — on a new value, bump slow then write."

TRIGGERS When you see ___ → reach for ___

sorted array, remove duplicates in placeslow/fast two pointers
"return new length k, O(1) space"write head + return slow + 1
duplicates are adjacent (sorted)compare nums[fast] vs nums[slow]
"filter in place, keep order"slow = write index, fast = reader

SKELETON The reusable shape

skeleton.ts
if (nums.length === 0) return 0;
let slow = 0;
for (let fast = 1; fast < nums.length; fast++) {
  if (nums[fast] !== nums[slow]) {
    slow++;
    nums[slow] = nums[fast];
  }
}
return slow + 1;

FLASHCARDS Tap to flip

Why does sortedness make this easy?
Equal values are contiguous, so a value is new exactly when it differs from the last kept one.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What does the slow pointer represent?
QUESTION 02
For nums = [0,0,1,1,1,2,2,3,3,4], what is k?
QUESTION 03
When fast finds a value EQUAL to nums[slow], you should:
QUESTION 04
What is the correct order of operations on a new value?
QUESTION 05
Time and space complexity?
QUESTION 06
Why does this approach require the array to be sorted?
QUESTION 07
After the function returns, the elements at indices ≥ k are:
QUESTION 08
#26 · Remove Duplicates from Sorted ArrayA slow write-pointer and a fast scan-pointer compact a sorted array in place: whenever the fast value differs from the last kept one, write it forward. Returns the count of unique values in O(n) time, O(1) space.Which algorithmic approach does this primarily use?
QUESTION 09
#26 · Remove Duplicates from Sorted ArrayA slow write-pointer and a fast scan-pointer compact a sorted array in place: whenever the fast value differs from the last kept one, write it forward. Returns the count of unique values in O(n) time, O(1) space.Which implementation correctly solves it?