Two Pointers on Two Sequences

When a problem hands you two sequences (two sorted arrays, two strings, two lists of intervals), give each one its own pointer. At every step you compare the two current items, do something with them, and advance one or both pointers. The tricky part is the advance rule: it must never skip an item that could still matter.

The idea#

Each pointer marks "everything before me is fully handled". You advance a pointer only when its current item can't take part in any future result. Because every step moves at least one pointer, the total work is $O(m + n)$ .

What changes between problems is the action and the advance rule. The four common shapes are:

Merge: compare the heads, take the smaller, advance that pointer.
Interval comparison: advance whichever interval ends first.
Subsequence check: on a match advance both; on a mismatch advance only the source.
Backward traversal: walk both from the end, with skip counters for characters that cancel.

How to spot it#

The giveaway is usually that the problem names two inputs and both are already in order. These cues suggest one pointer per sequence:

Two sorted inputs that must be merged or compared.
"Is t a subsequence of s?" or "how many characters must be appended to make it one?"
Two lists of intervals, each sorted and internally disjoint.
Merging into an array that already has spare room at the end.
Comparing two strings after edits such as backspaces, without building the edited strings.

Template#

Every shape follows the same loop. Only the action and the advance rule change.

i = j = 0
while i < len(a) and j < len(b):
    compare a[i] and b[j]
    act on them (take, record an overlap, count a match)
    advance the pointer whose item can't matter any more
    (advance both when both are used up)
handle whatever is left in a or b

Filling from the back#

The template walks forward, but one shape needs to walk backward. When the result goes into an array with spare slots at the end, walk both inputs from their last items.

i = last real item of a, j = last item of b
write = last slot of a
while j >= 0:                    # once b is used up, a is already in place
    if i >= 0 and a[i] > b[j]:
        a[write] = a[i], i -= 1
    else:
        a[write] = b[j], j -= 1
    write -= 1

Filling from the back works because the spare slots are at the back. The largest remaining value always goes to the last free slot, so nothing gets overwritten before it is read.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Messy overlap tests. Testing four separate "starts inside" and "ends inside" cases is error-prone. max(starts) <= min(ends) is the whole condition.
Advancing the wrong interval. Advance the one with the smaller end, so the other one stays around to overlap future intervals.
Leftovers after the loop. When one sequence runs out, the rest of the other still needs handling (copying, appending, or counting).
Merging from the front in place. You'd overwrite values you haven't read yet. If the free space is at the back, fill from the back.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Merge Sorted Array

nums1 has n spare slots at the end, so fill from the back. The loop can stop when nums2 is used up; what is left of nums1 is already in place.

Hint: Merge Strings Alternately

Take one character from each while both have characters left, then append the leftover tail of the longer string. Slicing with the shorter length (word1[k:]) handles the tail cleanly, even when one string is empty.

Hint: Append Characters to String to Make Subsequence

Scan s with one pointer and t with another, and advance in t only on a match. Whatever remains unmatched in t must be appended, so the answer is len(t) - j.

Hint: Backspace String Compare

Walk both strings from the end. Each # adds 1 to a skip counter, and each skip consumes one real character. When both pointers rest on a real character, compare them. This is $O(1)$ space because you never build the edited strings.

Hint: Interval List Intersections

The overlap of the current pair is [max(starts), min(ends)]; record it when lo <= hi. Then advance the interval that ends first, because it can't overlap anything later.

Hint: Meeting Scheduler

This is interval intersection with a duration check. Sort both lists of slots first. Return the overlap if it is at least duration long; otherwise advance the slot that ends first.

Key takeaways#

One pointer per sequence; each step advances at least one, so the scan is $O(m + n)$ .
Advance a pointer only when its item can't be part of any later result.
For intervals, the overlap is [max(starts), min(ends)], and the interval that ends first moves on.
Merge in place from whichever end has the free space.
Handle the leftover tail of the longer sequence after the loop.

Core idea#

Give each of two sequences its own pointer. Compare the two current items and advance one or both. Every step moves a pointer, so the work is $O(m + n)$ .

Key points#

Each pointer marks "everything before me is handled".
Advance a pointer only when its item cannot be part of any later result.
Two intervals overlap when max(starts) <= min(ends). That is the whole test.
Advance the interval that ends first. The other may still overlap later intervals.
Spot it: two sorted inputs, "is t a subsequence of s", two interval lists, a merge target with spare room at the end.

Four shapes#

Shape	Advance rule	Example
Merge	take the smaller head, advance it	Merge Sorted Array (fill from the back)
Interval comparison	advance the one that ends first	Interval List Intersections, Meeting Scheduler
Subsequence check	match: both; mismatch: source only	Append Characters: answer `len(t) - j`
Backward traversal	skip counters for canceled characters	Backspace String Compare, $O(1)$ space

Template#

i = j = 0
while i < len(a) and j < len(b):
    compare a[i] and b[j]
    act on them (take, record an overlap, count a match)
    advance the pointer whose item can't matter any more
handle whatever is left in a or b

Pitfalls#

Four separate "starts inside / ends inside" tests. Use max(starts) <= min(ends).
Advancing the wrong interval. Advance the smaller end.
Leftovers after the loop. Copy, append or count the rest of the longer sequence.
Merging in place from the front. You overwrite unread values. Fill from the end with the free space.

Say it in an interview#

"Each step advances at least one pointer, so the scan is O(m + n)."
"For intervals, the overlap is max of starts to min of ends, and the one that ends first moves on."