cf.completefrontend
TWO POINTERS · FOUNDATION

Read and write pointers

Walk a list with a read index while a slower write index copies only the items you keep, so the list is cleaned in place.

Time O(n)Space O(1)7 practice problemsStep-through picture

The idea

Sometimes you must remove items from a list without making a new list: drop the duplicates, drop the zeros, drop the muted users. Calling splice for each removal is slow, because every removal shifts all the later items.

Instead, use two indexes that both move forward. read visits every item once. write points to the next free spot for an item you want to keep. When read finds an item to keep, copy it to nums[write] and move write one step. Items you don't keep are simply skipped.

When read reaches the end, the first write items are exactly the kept items, in their original order. write is the new length. Nothing after it matters, so you can cut the list there.

An everyday example

Re-packing a bookshelf

You want to remove every damaged book from a shelf without leaving gaps. You walk along the shelf with your left hand on the next empty spot at the start, and your right hand checking each book in turn. A good book goes into the spot under your left hand, and your left hand moves one spot right. A damaged book is set aside. At the end, all the good books sit together at the start of the shelf, in the same order.

How the example maps to the code
In the exampleIn the code
Your right hand checking each bookread
Your left hand on the next empty spotwrite
Putting a good book in the empty spotnums[write] = nums[read]
The left hand moves to the next spotwrite++
How many good books are leftreturn write

From the slow way to read and write pointers

  1. Start with the easy way to drop repeats: build a new array and push each value that differs from the last one pushed. It is correct and O(n), but it uses O(n) extra memory, and the question says to change the array in place.
  2. The obvious in-place way is splice: delete each repeat where it stands. But every splice shifts all the later items one slot left. For 10,000 copies of the same value, removing 9,999 of them shifts 49,985,001 items in total. That is O(n^2) work for a one-pass problem.
  3. Notice where the kept items end up: all together at the front, in their original order. The first kept item goes to index 0, the second to index 1, and so on. So you don't need to shift anything: when you find a kept item, write it straight into the next free slot at the front.
  4. That needs two indexes moving forward at different speeds. read visits every item. write marks the next free slot and moves only when something is kept. Since write never passes read, a write only lands on a slot that has already been read. That loop is read and write pointers.

How it works

  1. Handle the empty list first: there is nothing to keep, so return 0.
  2. Start write at the first spot that might change. For removing repeats from a sorted list, the first item always stays, so write = 1.
  3. Move read from left to right over every item.
  4. Decide if nums[read] stays. For repeats: it stays when it differs from the last kept item, nums[write - 1].
  5. If it stays, copy it: nums[write] = nums[read], then write++.
  6. When read reaches the end, return write, the number of kept items.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function removeDuplicates(nums) {
  2. if (nums.length === 0) return 0;
  3. let write = 1;
  4. for (let read = 1; read < nums.length; read++) {
  5. if (nums[read] !== nums[write - 1]) {
  6. nums[write] = nums[read];
  7. write++;
  8. }
  9. }
  10. return write;
  11. }

How fast it is

TimeO(n)
Extra memoryO(1)

read passes over the list once and each step does a constant amount of work. Only two indexes are stored.

  • Best caseO(n)

    Every input still needs read to visit each item once. All-equal lists, like [5, 5, 5, 5], do the least work: no copies at all.

  • Average caseO(n)

    Any sorted list: one comparison per item, plus at most one copy.

  • Worst caseO(n)

    All values distinct, like [1, 2, 3, 4]: every item is copied, each onto itself because write === read. That is still one step per item.

Common mistakes

  • Comparing nums[read] with nums[read - 1] instead of the last kept item. It happens to work for repeats in a sorted list, but breaks for rules like "keep at most two". Compare with what you kept: nums[write - 1] or nums[write - 2].
  • Calling splice inside the loop. The indexes shift under you, items get skipped, and the work becomes O(n²).
  • Returning the array without cutting it when the question wants the array itself. Set nums.length = write so the leftover items at the end disappear.
  • Starting write at 0 while also keeping the first item automatically, which copies the first item twice.

When to use it

Look for these clues in a problem:

  • The question says "in place" or "with O(1) extra memory" and asks you to remove or filter items.
  • The kept items must stay in their original order.
  • The answer is a new length, and only the first part of the array matters afterwards.
  • The list is sorted and you must remove repeats, or keep each value at most a few times.

Check yourself

Answer each one in your head first, then open it.

Why is it safe to write into nums[write] while still reading the same array?

write moves at most once per step and read moves every step, so write <= read. The slot being written has already been read, so nothing unread is lost.

Why compare with nums[write - 1] and not nums[read - 1]?

nums[write - 1] is the last value actually kept. For removing repeats both happen to work, but for rules like "keep at most two", only comparing with the kept part gives the right answer.

What is in nums after the loop, past index write - 1?

Leftover values from the original array, which may include repeats. They don't matter; cut them off with nums.length = write if the caller needs a clean array.

How many copies does [1, 1, 2, 3, 3] cause?

Two: 2 is copied to index 1, and 3 is copied to index 2. The repeats of 1 and 3 are skipped, and the answer is 3.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps two promises at the start of each step. First, nums[0] to nums[write - 1] holds each distinct value of nums[0] to nums[read - 1] once, in order. Second, write <= read. At the start, read and write are both 1, and the first item alone is trivially distinct, so both hold.

Each step keeps them. Because the list is sorted, equal values sit next to each other, so nums[read] is a repeat exactly when it equals the last kept value, nums[write - 1]. A repeat is skipped and the kept part is still right. A new value is written to nums[write], which is at or before read, so it only overwrites an item that was already read. Then write++ and read++ keep write <= read.

The loop ends after read has visited every index once. Then the first promise covers the whole list: the first write slots hold every distinct value once, in order, and write is how many there are.

Going deeper

3 more ideas

Why copying never destroys an unread item

write never moves faster than read: it moves at most once per step, and read moves every step. So write <= read is always true, and nums[write] = nums[read] only writes to a spot that read has already passed. No item is overwritten before it is read.

Why it takes O(n) time and O(1) memory

read visits each item once, and each visit does one comparison and at most one copy. Calling splice for each removal would shift later items every time, which costs O(n²) in the worst case. The two indexes are the only extra memory.

Changing the keep rule

The loop stays the same; only the test on nums[read] changes. To drop a value, keep items where nums[read] !== value. To keep each value at most twice in a sorted list, keep items where write < 2 || nums[read] !== nums[write - 2]. To move zeros to the end, keep the non-zero items, then fill the rest of the list with zeros.

Work it by hand

Every step in a table, with why

Remove repeats from a sorted list where one value appears three times. The last column shows the kept part, nums[0] to nums[write - 1].

nums = [4, 4, 7, 7, 7, 10, 13, 13]

Stepreadnums[read]nums[write - 1]Keep?write afterKept partWhy
1144no1[4]nums[0] is always kept, so write starts at 1. The 4 at index 1 equals the last kept item, so skip it.
2274yes2[4, 7]7 is new: copy it into nums[1] and move write to 2. This write overwrites the extra 4 that read already passed.
3377no2[4, 7]A repeat of the last kept item. read moves on; write waits.
4477no2[4, 7]A third 7, also skipped. Now read is 2 ahead of write.
55107yes3[4, 7, 10]10 is new: copy it into nums[2], over a 7 that was already read.
661310yes4[4, 7, 10, 13]13 is new: copy it into nums[3].
771313no4[4, 7, 10, 13]The last item repeats 13, so skip it. read reaches the end and the loop stops.

It returns 4, and nums is now [4, 7, 10, 13, 7, 10, 13, 13]. Only the first 4 slots matter; the rest are leftovers you can cut with nums.length = write.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Read and write pointersO(n)O(1)The question says "in place", or you are cleaning a large array every frame and want to avoid creating new arrays.
filter into a new arrayO(n)O(n)Extra memory is fine and you'd rather not change the original array, which is the usual case in React state updates.
splice each removalO(n^2)O(1)Only for a handful of removals from a short list. Each splice shifts every later item.
[...new Set(nums)]O(n)O(n)The list is unsorted and you want each value once. The first copy of each value wins, but it builds a new array.

Extra memory: O(1): just read and write. The kept items reuse the input array's own slots.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Read and write pointers and the other approaches, on a scale where each line up is 10 times more steps.
  • Read and write pointers, filter into a new array, [...new Set(nums)] O(n)
  • splice each removal O(n^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Read and write pointers101,0001 million
filter into a new array101,0001 million
splice each removal1001 million1 trillion
[...new Set(nums)]101,0001 million

Inputs that need care

5 tricky inputs
An empty list: nums = []
The first line returns 0. Without it, write = 1 would claim one kept item that doesn't exist.
One item: nums = [8]
The loop starts at read = 1, which is already past the end, so it returns 1.
All equal: nums = [5, 5, 5, 5]
Every comparison finds a repeat, nothing is copied, and the answer is 1.
An unsorted list: nums = [2, 1, 2]
The two 2s aren't next to each other, so the second one doesn't match the last kept item, 1. It returns 3 and keeps both. Sort first, or use a Set of seen values.
NaN, 0, and -0
NaN !== NaN is true, so [NaN, NaN] keeps both and returns 2. 0 !== -0 is false, so [-0, 0] treats them as the same value and returns 1. Use Object.is if those cases matter.

Variations and follow-ups

Twists interviewers add

Keep each value at most twice

Compare with the item two places back in the kept part: keep nums[read] when write < 2 || nums[read] !== nums[write - 2]. The same idea with write - k allows k copies of each value.

Remove one value

To drop every 0, or every muted user id, start write at 0 and keep items where nums[read] !== value. The list doesn't need to be sorted for this one, because the rule doesn't look at neighbors.

Move zeros to the end

Keep the non-zero items with the same loop, then fill nums[write] to the end with 0. The non-zero items stay in their original order.

Filter in place by any rule

Any keep test that looks only at the current item works: if (keep(nums[read])) nums[write++] = nums[read];, then nums.length = write. This is an in-place filter, useful in hot loops where creating new arrays every frame is too costly.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "in place", "return the new length", or "O(1) extra memory" together with removing, filtering, or compacting items while keeping their order.
  • Explain the safety rule out loud: "write never passes read, so I only overwrite slots I've already read." Interviewers often ask why the copy can't destroy data, and that sentence answers it.
  • Test by hand: an empty list, a list with no repeats (every item copies onto itself), and a list that is all one value.
  • Expect the follow-up "now keep each value at most twice". Change only the keep test, to write < 2 || nums[read] !== nums[write - 2], and explain why comparing with the kept part, not with nums[read - 1], is what makes it work.

Where frontend code uses it

The same idea in real UI code
  • Removing finished items from a large array of animations or timers each frame without making a new array, which avoids extra garbage collection in a game loop or canvas renderer.
  • Cleaning a sorted list of selected row ids so each id appears once before sending it to an API.
  • Array.prototype.filter keeps the same items in the same order, but builds a new array. The read and write pattern is the in-place version.

Related algorithms