Two Pointers & Windows

Two Pointers (Read/Write)

A slow write pointer and a fast read pointer for in-place filtering and partitioning.

Medium, about 60 minutes to practise.

1Understand

The idea

A fast pointer reads every element; a slow pointer marks where the next kept element should be written. Everything before the slow pointer is the finished result. This filters, deduplicates or partitions an array in place in one pass with O(1) extra space.

Intuition

A fast pointer reads every element; a slow pointer marks where the next kept element should be written. Everything before the slow pointer is the finished result. This filters, deduplicates or partitions in place in one pass with O(1) extra space.

The invariant is the whole story: after each step, a[:write] is the answer so far. Partition problems (Dutch flag, move zeros) use the same idea with more boundary indices.

When merging two sorted arrays into one buffer. Write from the back so you do not overwrite unread values.

What you will be able to do

  • Maintain a read/write invariant
  • Partition arrays in place

When to use it

  • Remove or move elements in place
  • Return the new length
  • O(1) extra space required

2See it

Walkthrough

Remove zeros in place

nums = [0, 1, 0, 3, 2], slow writes kept values; fast reads everything.

1 / 7

SF
0
1
0
3
2
01234
S → index 0F → index 0

slow marks the next write slot. fast = 0 sees 0 → skip (do not write).

if nums[fast] != 0: ...

Live template

Line 1 active

1write = 0
2for read in range(len(a)):
3 if keep(a[read]):
4 a[write] = a[read]; write += 1
5return write

Complexity: time O(n), space O(1)

Time O(n), extra space O(1). Building a new list is simpler but fails "in-place" constraints. For 3-way partition, three indices keep the same linear bound. Merging from the front into a shared buffer is the classic overwrite bug.

Read the walkthrough as text

Remove duplicates from sorted array. a = [0,0,1,1,1,2,2].

  1. write = 1 (first element always kept).
  2. read scans from 1..n-1; whenever a[read] != a[write-1], copy to a[write] and advance write.
  3. End state: a[:write] = [0,1,2], return write == 3.

In code:

  • write = 1
  • for read in range(1, len(a)):
  • if a[read] != a[write - 1]:
  • a[write] = a[read]
  • write += 1

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Remove elements in place

    Example. Remove all instances of val; return new length.

    How. Write pointer only advances when nums[read] should be kept; overwrite in place.

  • Remove duplicates from sorted array

    Example. In-place unique count for a sorted array.

    How. Write position 0 fixed; copy nums[read] when read > 0 and different from last written.

  • Move zeroes

    Example. Push all zeros to the end while keeping relative order of nonzeros.

    How. Same read/write: swap or assign nonzeros to write index, then fill tail with zero.

  • Dutch national flag (3-way partition)

    Example. Sort array of 0, 1, 2 in one pass.

    How. Three pointers: mid scans, low swaps 0s, high swaps 2s.

  • Merge sorted arrays from the back

    Example. Merge into nums1 with extra space at the end.

    How. Write pointer at the end; pick larger from A[i], B[j] and move backward to avoid overwrite.

  • Subsequence check across two sequences

    Example. Is s a subsequence of t?

    How. Advance read on t when it matches s[write]; success when write reaches len(s).

  • Resolve forces from both sides (dominoes)

    Example. Simulate domino push left/right on a string.

    How. Two scans from ends with force counters; R and L meet with the stronger force winning.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Extra array

    Why it happens. Building a new list is easier than maintaining the write invariant.

    How it fails. Remove duplicates by appending to `out`, works logically but fails “in-place O(1) space”.

    Fix. Keep write index; overwrite nums[write] and return write length.

  • Broken invariant

    Why it happens. The write pointer advances when the element should be skipped (or vice versa).

    How it fails. Remove val: you advance write on every element including matches, duplicates remain.

    Fix. Only write when `keep(x)`; read always advances. Write only on kept elements.

  • Forward overwrite

    Why it happens. Merging from the front overwrites unread tail of the longer array.

    How it fails. Merge in place from index 0: first written value clobbers an element you still need to read.

    Fix. Merge from the end (backward write index) or use extra buffer when merging forward.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons