Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Two pointers

A reader and a writer

Lesson · 10 min read · Two pointers · A reader and a writer

Both pointers go left to right. One reads every element, the other marks where the next kept value goes, and the array is rewritten in place.

Filtering without a second array

You'll find that a lot of array questions come down to keeping some of the values in the order they came in and doing it in place. You could build a new list and copy it back at the end and in a real codebase that's probably what I'd do myself, but in an interview you'll usually be asked for O(1) extra space and that's when you want two pointers that both go left to right.

The reader r looks at every element once and the writer w is the length of the part you've decided to keep, so nums[0..w−1] is always your answer so far. Each time the reader finds a value you want you put it at nums[w] and move w up by one. The writer can't ever get ahead of the reader, which is why you never write over a value you haven't read yet.

Reader and writer

filter(nums)

  1. Set w = 0.
  2. For r from 0 to n − 1: if nums[r] should be kept, set nums[w] = nums[r] and add one to w.
  3. Return w, the length of the kept prefix.

Moving the zeros to the end is the same loop with a swap where the copy was. The zeros you skip over get carried along to the back and you don't have to write them in at the end.

Looking back at what you kept

Say you're allowed to keep each value at most twice in a sorted array. The thing I'd want you to see is that the rule for keeping a value looks back at what you've kept so far. If nums[w − 2] is already equal to the value you're reading then you've kept two copies and this one can go. The array's sorted so those two copies would have to be the last two you kept, and that's why a single comparison is enough. If you change the 2 to a k you've got code that keeps each value at most k times.

Each value at most twice in [3, 3, 3, 3, 5, 6, 6, 6].

  1. Step 1 / 10
    nums
    30w/r31323354656667
    w0

    w is the length of the kept prefix. A value is kept unless nums[w − 2] already equals it.

  2. Step 2 / 10
    nums
    30w/r31323354656667
    w1r0

    w = 0 < 2: keep 3.

  3. Step 3 / 10
    nums
    3031w/r323354656667
    w2r1

    w = 1 < 2: keep 3.

  4. Step 4 / 10
    nums
    303132w/r3354656667
    w2r2

    nums[r] = 3 = nums[w − 2]: two copies are already kept. Skip it.

  5. Step 5 / 10
    nums
    303132w33r54656667
    w2r3

    nums[r] = 3 = nums[w − 2]: two copies are already kept. Skip it.

  6. Step 6 / 10
    nums
    303152w3354r656667
    w3r4

    nums[r] = 5 ≠ nums[w − 2] = 3: keep it at position 2.

  7. Step 7 / 10
    nums
    30315263w5465r6667
    w4r5

    nums[r] = 6 ≠ nums[w − 2] = 3: keep it at position 3.

  8. Step 8 / 10
    nums
    3031526364w6566r67
    w5r6

    nums[r] = 6 ≠ nums[w − 2] = 5: keep it at position 4.

  9. Step 9 / 10
    nums
    303152636465w6667r
    w5r7

    nums[r] = 6 = nums[w − 2]: two copies are already kept. Skip it.

  10. Step 10 / 10
    nums
    3031526364
    w5

    The kept prefix has length 5: 3, 3, 5, 6, 6.

Three regions and three pointers

When you have to sort an array of 0s, 1s and 2s in one pass you're using the same idea with a writer at each end. Everything before lo is a 0 and everything after hi is a 2. The part from lo up to mid holds the 1s and what's left from mid to hi is what you haven't read yet. You swap a 0 down to lo and a 2 up to hi and you leave a 1 where it is.

The trap people fall into comes after you swap with hi. The value you get back from the far end hasn't been read yet so you have to leave mid where it is and look at it again. After a swap with lo you can move on because whatever was sitting at lo has been read already and it has to be a 1.

TimeO(n)
SpaceO(1) extra

You read every element once. Merging two sorted arrays works the same way with a pointer on each array, and if you're merging into the first array and the spare room is at its end you'll want to fill it from the back so you don't write over anything you still need.

Sorting [1, 2, 0, 2, 1, 0] in one pass.

  1. Step 1 / 8
    nums
    10lo/mid2102231405hi
    lo0mid0hi5

    Everything is unread: the window [mid, hi] is the whole array.

  2. Step 2 / 8
    nums
    10lo/mid2102231405hi
    lo0mid1hi5

    nums[mid] = 1: already in the middle region. mid advances.

  3. Step 3 / 8
    nums
    10lo01mid02231425hi
    lo0mid1hi4

    nums[mid] = 2: swap it to position hi = 5; hi moves left. mid stays: the value that came from hi is unread.

  4. Step 4 / 8
    nums
    00lo11mid022314hi25
    lo1mid2hi4

    nums[mid] = 0: swap it to position lo = 0; lo and mid both advance.

  5. Step 5 / 8
    nums
    0001lo12mid2314hi25
    lo2mid3hi4

    nums[mid] = 0: swap it to position lo = 1; lo and mid both advance.

  6. Step 6 / 8
    nums
    000112lo13mid24hi25
    lo2mid3hi3

    nums[mid] = 2: swap it to position hi = 4; hi moves left. mid stays: the value that came from hi is unread.

  7. Step 7 / 8
    nums
    000112lo13mid/hi2425
    lo2mid4hi3

    nums[mid] = 1: already in the middle region. mid advances.

  8. Step 8 / 8
    nums
    000112132425
    lo2mid4hi3

    mid has passed hi: nothing is unread, and the array is sorted.

Problems in this module