Two pointers: converging and reader–writer

Two pointers is a way to scan a sequence with two indices instead of one. Each index marks a position, and on every step a rule moves one of them. The rule is chosen so that every move rules out candidates that can be proved useless, so the scan takes about n steps where two nested loops would try about n²/2 pairs. It works when the data has an order (values sorted from smallest to largest), a symmetry (a word that should read the same backwards), or a job that can be done in place (keep some items, drop the rest).

The pattern has three shapes: converging pointers that start at both ends and move inward, reader–writer pointers that move the same way through one list, and parallel scans that walk two sorted lists side by side. This lesson shows when each one applies and the invariant that makes its moves safe. Then it solves one problem in full, two files whose sizes add up to exactly the space left on a drive, from the brute force to code in four languages and a bug that only large sizes expose.

When two pointers apply

The problem statement usually gives the shape away:

• Converging pointers: the values are sorted and you need two of them with a given sum, difference or best fit; or the statement says “reads the same backwards” or “reverse in place”, or compares the first item with the last.
• Reader–writer pointers: you must remove, keep or move items in place, with O(1) extra memory.
• A parallel scan: there are two sorted lists to merge, to search for the items they share, or to check that one is a subsequence of the other.

Some similar-looking problems belong to other patterns:

• Unsorted data where the answer is a position. Sorting first costs O(n log n) and moves values away from their positions, so sort (value, position) pairs, or use one pass with a hash map, the approach of the arrays and hashing module. If you sort in JavaScript, pass a comparison, values.sort((a, b) => a - b): without one, sort() compares numbers as text, so 80 comes before 9.
• A contiguous stretch that obeys a rule, such as the longest run of days under a budget. That is a sliding window, the next module: two pointers that move the same way and bound the stretch between them.
• Fast and slow pointers walk a linked list at two speeds to find its middle or a cycle; the linked lists module covers them.

Three shapes, one idea

In every shape the loop keeps the list split into parts with fixed meanings, and every move shifts one boundary between parts:

• Converging pointers start at the two ends, lo = 0 and hi = n − 1, and each step moves one of them inward until they meet. The invariant: everything outside lo..hi is dealt with, ruled out in a pair search or already matched in a palindrome. They fit sorted values and symmetric data: pair sums, palindromes, reversing in place.
• Reader–writer pointers both start at 0 and move right: read on every step, write only when an item is kept. The invariant: a[:write] holds the kept items, in their original order. They fit editing one list in place: removing, deduplicating, compacting.
• A parallel scan puts i at the start of one sorted list and j at the start of another, and moves the pointer at the smaller value, or both on a match, until either list runs out. The invariant: everything before i and j is settled. It fits merging, intersecting and subsequence checks.

All three take O(n) time, or O(n + m) for two lists, and O(1) extra memory besides any output, because each step moves at least one pointer, always in its own direction and never back. What differs between the shapes is the reason a move is safe. That reason is the invariant, and in an interview it is the sentence you should be able to say aloud.

A problem solved in full: two files that fill a drive

Four examples, which every version of the code below runs:

1. sizes = [1, 3, 4, 6, 8, 11, 15] and space = 14 give (1, 5), because 3 + 11 = 14. (3, 4), for 6 + 8, would be just as correct.
2. sizes = [4, 6, 9] and space = 12 give (-1, -1). 6 + 6 would be 12, but there is only one file of 6 bytes.
3. sizes = [5, 5] and space = 10 give (0, 1): two files of the same size are still two files.
4. sizes = [700000000, 1300000000, 1500000000] and space = 2000000000 give (0, 1). Each of these numbers fits in a 32-bit integer, but the sum 700,000,000 + 1,500,000,000 does not, which matters in Java and C++.

The brute force: every pair

Try every pair i < j and stop at the first one that fits. It is plainly correct, which makes it the reference to test a faster version against, but on n files it computes up to n(n − 1)/2 sums: 19,999,900,000 for n = 200,000. At the rough budgets of the lesson on constraints, a hundred million simple operations a second in C++ and ten million in CPython, that is over three minutes of C++ and over half an hour of Python.

What to notice

Because the sizes are sorted, the sum sizes[lo] + sizes[hi] works like a dial. Moving lo one place right can only make it larger or keep it the same; moving hi one place left can only make it smaller or keep it the same. Start at the two ends, and every comparison with space tells you which way to turn the dial.

Two pointers in O(n)

1. Start with lo = 0 and hi = n − 1.
2. While lo < hi, compute total = sizes[lo] + sizes[hi].
3. If total equals space, return (lo, hi).
4. If total is smaller, move lo one place right; if it is larger, move hi one place left.
5. When lo meets hi, return (-1, -1).

Why no pair is skipped

The loop keeps one invariant: no pair that fills the drive has i < lo or j > hi. The three arguments of the lesson on dry runs and invariants prove that the search is correct:

1. Initialisation. At the start lo is 0 and hi is n − 1, and no position lies below 0 or above n − 1, so the invariant holds.
2. Maintenance. Suppose total is smaller than space. Every position j with lo < j ≤ hi holds a size of at most sizes[hi], because the list is sorted, so sizes[lo] + sizes[j] is at most total, which is too small. Pairs with j > hi are ruled out already, so no pair that fills the drive starts at lo, and lo may move on. If total is larger than space, the mirror argument shows that no pair that fills the drive ends at hi, so hi may move back.
3. Termination. Every step makes hi − lo one smaller, so the loop ends after at most n − 1 sums. When lo meets hi, every pair i < j has i < lo or j > hi, so the invariant says that no pair fills the drive, and (-1, -1) is the right answer.

Picture every pair as a cell of a table, with i down the side and j across the top. Each move crosses out what is left of one row or one column, at the cost of one sum, and that is why n − 1 sums are enough where the brute force needs n(n − 1)/2.

A dry run

The first two examples, traced one sum per row:

"""A dry run of the two-pointer search: one row of the trace table per sum."""


def fill_exactly(sizes, space):
    print(f"sizes = {sizes}, space = {space}")
    print(" lo  hi  sizes[lo]  sizes[hi]  total  move")
    lo, hi = 0, len(sizes) - 1
    while lo < hi:
        total = sizes[lo] + sizes[hi]
        if total == space:
            move = "found"
        elif total < space:
            move = "too small, so lo += 1"
        else:
            move = "too large, so hi -= 1"
        print(f"{lo:3} {hi:3} {sizes[lo]:10} {sizes[hi]:10} {total:6}  {move}")
        if total == space:
            return lo, hi
        if total < space:
            lo += 1
        else:
            hi -= 1
    print(f"{lo:3} {hi:3}  lo == hi: no pair is left to try")
    return -1, -1


print(fill_exactly([1, 3, 4, 6, 8, 11, 15], 14))
print()
print(fill_exactly([4, 6, 9], 12))

sizes = [1, 3, 4, 6, 8, 11, 15], space = 14
 lo  hi  sizes[lo]  sizes[hi]  total  move
  0   6          1         15     16  too large, so hi -= 1
  0   5          1         11     12  too small, so lo += 1
  1   5          3         11     14  found
(1, 5)

sizes = [4, 6, 9], space = 12
 lo  hi  sizes[lo]  sizes[hi]  total  move
  0   2          4          9     13  too large, so hi -= 1
  0   1          4          6     10  too small, so lo += 1
  1   1  lo == hi: no pair is left to try
(-1, -1)

In the first input the opening sum, 1 + 15 = 16, is too large, so hi moves and 15 is ruled out: it is too large even with the smallest size. Then 1 + 11 = 12 is too small, so lo moves and 1 is ruled out: it is too small even with the largest size left. The third sum fills the drive. The second input shows the other ending: after two moves the pointers meet, and the invariant says that no pair is left to try.

The code in four languages

The same function in Python, JavaScript, Java and C++. The Run button runs the Python and JavaScript versions in your browser:

"""Two files that fill a drive exactly: converging pointers on sorted sizes."""


def fill_exactly(sizes, space):
    """Return (i, j), i < j, with sizes[i] + sizes[j] == space, or (-1, -1)."""
    lo, hi = 0, len(sizes) - 1
    # Invariant: no pair that fills the drive has i < lo or j > hi.
    while lo < hi:
        total = sizes[lo] + sizes[hi]
        if total == space:
            return lo, hi
        if total < space:
            lo += 1  # too small even with the largest size left
        else:
            hi -= 1  # too large even with the smallest size left
    return -1, -1


print(fill_exactly([1, 3, 4, 6, 8, 11, 15], 14))
print(fill_exactly([4, 6, 9], 12))
print(fill_exactly([5, 5], 10))
print(fill_exactly([700_000_000, 1_300_000_000, 1_500_000_000], 2_000_000_000))

(1, 5)
(-1, -1)
(0, 1)
(0, 1)

// Two files that fill a drive exactly: converging pointers on sorted sizes.

/** [i, j] with i < j and sizes[i] + sizes[j] === space, or [-1, -1]. */
function fillExactly(sizes, space) {
  let lo = 0;
  let hi = sizes.length - 1;
  // Invariant: no pair that fills the drive has i < lo or j > hi.
  while (lo < hi) {
    const total = sizes[lo] + sizes[hi]; // exact up to 2 ** 53 - 1
    if (total === space) return [lo, hi];
    if (total < space) lo += 1; // too small even with the largest size left
    else hi -= 1; // too large even with the smallest size left
  }
  return [-1, -1];
}

const show = ([i, j]) => console.log(`(${i}, ${j})`);
show(fillExactly([1, 3, 4, 6, 8, 11, 15], 14));
show(fillExactly([4, 6, 9], 12));
show(fillExactly([5, 5], 10));
show(fillExactly([700_000_000, 1_300_000_000, 1_500_000_000], 2_000_000_000));

(1, 5)
(-1, -1)
(0, 1)
(0, 1)

// Two files that fill a drive exactly: converging pointers on sorted sizes.
public class PairSum {
    /** {i, j} with i < j and sizes[i] + sizes[j] == space, or {-1, -1}. */
    static int[] fillExactly(int[] sizes, int space) {
        int lo = 0, hi = sizes.length - 1;
        // Invariant: no pair that fills the drive has i < lo or j > hi.
        while (lo < hi) {
            // 64-bit sum: two ints can add up to more than an int holds.
            long total = (long) sizes[lo] + sizes[hi];
            if (total == space) return new int[] {lo, hi};
            if (total < space) lo++;
            else hi--;
        }
        return new int[] {-1, -1};
    }

    static void show(int[] pair) {
        System.out.println("(" + pair[0] + ", " + pair[1] + ")");
    }

    public static void main(String[] args) {
        show(fillExactly(new int[] {1, 3, 4, 6, 8, 11, 15}, 14));
        show(fillExactly(new int[] {4, 6, 9}, 12));
        show(fillExactly(new int[] {5, 5}, 10));
        int[] big = {700_000_000, 1_300_000_000, 1_500_000_000};
        show(fillExactly(big, 2_000_000_000));
    }
}

// Two files that fill a drive exactly: converging pointers on sorted sizes.
#include <cstdint>
#include <print>
#include <utility>
#include <vector>

// {i, j} with i < j and sizes[i] + sizes[j] == space, or {-1, -1}.
std::pair<int, int> fill_exactly(const std::vector<int>& sizes, int space) {
    int lo = 0, hi = static_cast<int>(sizes.size()) - 1;
    // Invariant: no pair that fills the drive has i < lo or j > hi.
    while (lo < hi) {
        // 64-bit sum: two ints can add up to more than INT_MAX.
        std::int64_t total = std::int64_t{sizes[lo]} + sizes[hi];
        if (total == space) return {lo, hi};
        if (total < space) ++lo;
        else --hi;
    }
    return {-1, -1};
}

int main() {
    const std::vector<std::pair<std::vector<int>, int>> examples = {
        {{1, 3, 4, 6, 8, 11, 15}, 14},
        {{4, 6, 9}, 12},
        {{5, 5}, 10},
        {{700'000'000, 1'300'000'000, 1'500'000'000}, 2'000'000'000},
    };
    for (const auto& [sizes, space] : examples) {
        auto [i, j] = fill_exactly(sizes, space);
        std::println("({}, {})", i, j);
    }
}

The Java and C++ versions are run with the commands you would type in a terminal:

"""Runs the Java version, then builds and runs the C++ version."""
from terminal import run

run("""
java --version | head -n 1 | cut -d ' ' -f 1,2
java PairSum.java
clang++ --version | head -n 1
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined pair_sum.cpp -o pair_sum
./pair_sum
""")

$ java --version | head -n 1 | cut -d ' ' -f 1,2
openjdk 27
$ java PairSum.java
(1, 5)
(-1, -1)
(0, 1)
(0, 1)
$ clang++ --version | head -n 1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined pair_sum.cpp -o pair_sum
$ ./pair_sum
(1, 5)
(-1, -1)
(0, 1)
(0, 1)

Each language needs a moment’s thought about the sum, which can reach 4,000,000,000:

• Python integers have unlimited precision, so sizes[lo] + sizes[hi] is always exact.
• JavaScript numbers are 64-bit floating-point values, and every integer up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1 (about 9 × 10¹⁵), is exact, far above any sum here.
• Java and C++ keep the sizes in 32-bit ints, whose largest value is 2,147,483,647, and add them in 64 bits: (long) sizes[lo] + sizes[hi] in Java, std::int64_t{sizes[lo]} + sizes[hi] in C++. The conversion must come before the addition; (long) (sizes[lo] + sizes[hi]) would convert a sum that has already gone wrong.
• java PairSum.java compiles and runs a single source file in one step, which the java command has done since Java 11 (JEP 330). The C++ version uses std::println, so it needs -std=c++23; the sanitizer flags turn mistakes such as the one in the next section into reports at run time.

A bug that only large sizes expose

Here are the same searches with the sum kept in an int, run on the fourth example:

// The same search with the sum kept in an int: right for small sizes,
// wrong once two sizes add up to more than Integer.MAX_VALUE.
public class IntSum {
    static int[] fillExactly(int[] sizes, int space) {
        int lo = 0, hi = sizes.length - 1;
        while (lo < hi) {
            // The bug: an int sum wraps around above 2,147,483,647.
            int total = sizes[lo] + sizes[hi];
            System.out.println("lo = " + lo + ", hi = " + hi + ", total = " + total);
            if (total == space) return new int[] {lo, hi};
            if (total < space) lo++;
            else hi--;
        }
        return new int[] {-1, -1};
    }

    public static void main(String[] args) {
        int[] big = {700_000_000, 1_300_000_000, 1_500_000_000};
        int[] pair = fillExactly(big, 2_000_000_000);
        System.out.println("(" + pair[0] + ", " + pair[1] + ")");
    }
}

// The same search with the sum kept in an int: signed overflow,
// which C++ leaves undefined.
#include <print>
#include <utility>
#include <vector>

std::pair<int, int> fill_exactly(const std::vector<int>& sizes, int space) {
    int lo = 0, hi = static_cast<int>(sizes.size()) - 1;
    while (lo < hi) {
        // The bug: two ints can add up to more than INT_MAX.
        int total = sizes[lo] + sizes[hi];
        if (total == space) return {lo, hi};
        if (total < space) ++lo;
        else --hi;
    }
    return {-1, -1};
}

int main() {
    const std::vector<int> big = {700'000'000, 1'300'000'000, 1'500'000'000};
    auto [i, j] = fill_exactly(big, 2'000'000'000);
    std::println("({}, {})", i, j);
}

"""Runs the two versions that keep the sum in an int."""
from terminal import run

run("""
java IntSum.java
clang++ -std=c++23 -fsanitize=undefined -fno-sanitize-recover=undefined int_sum.cpp -o int_sum
./int_sum
""")

$ java IntSum.java
lo = 0, hi = 2, total = -2094967296
lo = 1, hi = 2, total = -1494967296
(-1, -1)
$ clang++ -std=c++23 -fsanitize=undefined -fno-sanitize-recover=undefined int_sum.cpp -o int_sum
$ ./int_sum
int_sum.cpp:11:31: runtime error: signed integer overflow: 700000000 + 1500000000 cannot be represented in type 'value_type' (aka 'int')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior int_sum.cpp:11:31
[exit status 134]

Java defines what happens. Its language specification says that an int addition that overflows keeps the low-order 32 bits of the true sum and never throws an exception. So 700,000,000 + 1,500,000,000 = 2,200,000,000 becomes 2,200,000,000 − 2³², which is −2,094,967,296. That looks too small, the search moves lo past the answer and reports no pair, and nothing warns you.

C++ does not define it at all. In the C++ standard, an arithmetic result outside the range of its type is undefined behaviour, so the compiler may assume it never happens. Built with -fsanitize=undefined, Clang’s UndefinedBehaviorSanitizer reports the overflow and its line; -fno-sanitize-recover=undefined makes the program stop there instead of carrying on with a wrong value. Without a sanitizer nothing checks for it, and the program may print a wrong answer without a word.

Sample tests rarely catch this bug, because their numbers are small. Before you submit in Java or C++, ask how large a sum can get (here 4 × 10⁹) and compare it with 2,147,483,647.

Checking it against the brute force

A brute force is slow, but it is the easiest code to trust, so it makes a good judge for the fast version:

"""Checks the two-pointer search against the brute force on random lists,
then counts the sums that each one computes."""
import random


def brute_force(sizes, space):
    """Tries every pair i < j. Returns the pair, or (-1, -1), and the sums computed."""
    sums = 0
    for i in range(len(sizes)):
        for j in range(i + 1, len(sizes)):
            sums += 1
            if sizes[i] + sizes[j] == space:
                return (i, j), sums
    return (-1, -1), sums


def two_pointers(sizes, space):
    """The converging search. Returns the pair, or (-1, -1), and the sums computed."""
    sums = 0
    lo, hi = 0, len(sizes) - 1
    while lo < hi:
        sums += 1
        total = sizes[lo] + sizes[hi]
        if total == space:
            return (lo, hi), sums
        if total < space:
            lo += 1
        else:
            hi -= 1
    return (-1, -1), sums


def fills(sizes, space, pair):
    i, j = pair
    return 0 <= i < j < len(sizes) and sizes[i] + sizes[j] == space


# Small sizes with many repeats: duplicates, missing pairs and several
# correct answers all come up often.
rng = random.Random(7)
for _ in range(3000):
    sizes = sorted(rng.randint(1, 20) for _ in range(rng.randint(2, 9)))
    space = rng.randint(2, 40)
    slow, _ = brute_force(sizes, space)
    fast, _ = two_pointers(sizes, space)
    # Both find a pair or both find none, and a pair found fills the space.
    assert (slow == (-1, -1)) == (fast == (-1, -1)), (sizes, space)
    assert fast == (-1, -1) or fills(sizes, space, fast), (sizes, space)
print("3,000 random lists: the two searches agree on whether a pair exists")

# The worst case for both: no two sizes fill the space, so both run to the end.
for n in (500, 1_000, 2_000):
    sizes = list(range(1, n + 1))
    space = 2 * n + 1  # larger than any two sizes together
    _, slow = brute_force(sizes, space)
    _, fast = two_pointers(sizes, space)
    print(f"n = {n:>5,}: brute force {slow:>9,} sums, two pointers {fast:>5,}")

3,000 random lists: the two searches agree on whether a pair exists
n =   500: brute force   124,750 sums, two pointers   499
n = 1,000: brute force   499,500 sums, two pointers   999
n = 2,000: brute force 1,999,000 sums, two pointers 1,999

The random lists are short and full of repeated sizes on purpose, so duplicates, missing pairs and several correct answers all come up thousands of times. The check compares what the problem asks for, whether a pair exists and whether the pair found fills the space, because the two searches may find different correct pairs. The counts at the end show the two costs growing: doubling n multiplies the brute force’s sums by about four and only doubles the two-pointer search’s. At n = 200,000 the gap is 19,999,900,000 sums against 199,999.

Converging on symmetry: palindromes

A palindrome is the symmetric case of converging pointers: position i must match position n − 1 − i, and those are exactly the pairs that lo and hi visit.

"""Converging pointers on a symmetric shape: does a word read the same backwards?"""


def is_palindrome(word):
    lo, hi = 0, len(word) - 1
    # Invariant: word[:lo] is the mirror image of word[hi + 1:].
    while lo < hi:
        same = word[lo] == word[hi]
        verdict = "match" if same else "differ"
        print(f"  lo = {lo}, hi = {hi}: {word[lo]!r} and {word[hi]!r} {verdict}")
        if not same:
            return False
        lo += 1
        hi -= 1
    return True


for word in ["malayalam", "reviewer"]:
    print(word)
    print(f"  palindrome: {is_palindrome(word)}")

# Letters whatever their case: casefold() removes more differences than lower().
for method in ("lower", "casefold"):
    sigma, final_sigma, sharp_s = (getattr(c, method)() for c in "Σςß")
    label, same = method + "():", sigma == final_sigma
    print(f"{label:12} Σ → {sigma}, ς → {final_sigma}, equal: {same}; ß → {sharp_s}")

malayalam
  lo = 0, hi = 8: 'm' and 'm' match
  lo = 1, hi = 7: 'a' and 'a' match
  lo = 2, hi = 6: 'l' and 'l' match
  lo = 3, hi = 5: 'a' and 'a' match
  palindrome: True
reviewer
  lo = 0, hi = 7: 'r' and 'r' match
  lo = 1, hi = 6: 'e' and 'e' match
  lo = 2, hi = 5: 'v' and 'w' differ
  palindrome: False
lower():     Σ → σ, ς → ς, equal: False; ß → ß
casefold():  Σ → σ, ς → σ, equal: True; ß → ss

The invariant is that word[:lo] mirrors word[hi + 1:]. A mismatch settles the answer at once, as the third comparison in “reviewer” does, and when the pointers meet, the whole word mirrors. The loop makes at most n / 2 comparisons.

Real codes and names also contain spaces, punctuation and capitals. Move a pointer past each character that does not count, which str.isalnum() tells you, and compare letters with casefold() rather than lower(). The Python documentation describes casefolding as more aggressive than lowercasing, because it is meant to remove every case distinction. The last two lines of the output show the difference: lower() leaves the final sigma ς unchanged, so Σ and ς do not match, while casefold() turns both into σ, and ß into ss. The exercise at the end of this lesson puts these pieces together.

Reader–writer pointers: editing in place

The second shape keeps both pointers moving right through one list. read looks at every item once; write marks where the next item to keep goes. Here a shop’s list drops the items that are out of stock and keeps the others in their order:

"""Reader-writer pointers: drop the out-of-stock items in place, keeping the order."""


def drop_out_of_stock(items, stock):
    write = 0
    # Invariant: items[:write] are the in-stock items read so far, in order.
    for read in range(len(items)):
        keep = stock[items[read]] > 0
        if keep:
            items[write] = items[read]
            write += 1
        shown = f"{'keep' if keep else 'drop'} {items[read]!r}"
        print(f"read = {read}, write = {write}: {shown:16} {items[:write]}")
    del items[write:]  # what is left from write on are leftovers


stock = {"rice": 4, "lentils": 0, "flour": 2, "honey": 0, "salt": 9}
items = ["rice", "lentils", "flour", "honey", "salt"]
drop_out_of_stock(items, stock)
print(items)

read = 0, write = 1: keep 'rice'      ['rice']
read = 1, write = 1: drop 'lentils'   ['rice']
read = 2, write = 2: keep 'flour'     ['rice', 'flour']
read = 3, write = 2: drop 'honey'     ['rice', 'flour']
read = 4, write = 3: keep 'salt'      ['rice', 'flour', 'salt']
['rice', 'flour', 'salt']

The invariant is in the comment: items[:write] holds the in-stock items read so far, in their original order. A kept item is copied to position write, which is never ahead of read, so nothing is overwritten before it has been read. When the loop ends, del items[write:] cuts off the leftovers. The whole job is one scan: O(n) time and O(1) extra memory.

The tempting alternative is to delete each unwanted item where it stands. It is slower: removing an item from a Python list moves every item after it one place left, which is why the documentation gives pop(0) and insert(0, v) an O(n) cost, so a list with many unwanted items costs O(n²). Deleting from a list while a loop walks over it is also, in the words of the Python tutorial, “tricky to get right”.

Parallel scans: two sorted lists

The third shape gives each list a pointer of its own. To find the file IDs that appear in both of two sorted backup lists, compare a[i] with b[j]. Equal IDs are in both lists. The smaller ID cannot appear later in the other list, because everything left there is larger, so its pointer moves on. Trace this program by hand before you read its output:

"""A parallel scan: the file IDs that appear in both of two sorted backup lists."""


def common(a, b):
    i = j = 0
    both = []
    # Invariant: every ID of a[:i] and of b[:j] is settled: it is in both
    # lists, or it is known to be missing from the other one.
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            both.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1  # a[i] is smaller than every ID left in b
        else:
            j += 1  # b[j] is smaller than every ID left in a
    return both


monday = [102, 117, 125, 140, 161, 178]
tuesday = [99, 117, 140, 152, 178, 190]
print(common(monday, tuesday))

[117, 140, 178]

Every step moves at least one pointer, so the scan takes at most 6 + 6 = 12 steps here; it needs 8. With a different action at each step, the same loop merges two sorted lists, or checks whether one list is a subsequence of another.

Saying the invariant in an interview

Interviewers often ask why a move is safe. Answer with the elimination in one sentence: “The sum is too small, and sizes[hi] is the largest size left, so sizes[lo] cannot be in any answer; I move lo.” Then use the habit from the dry-runs lesson: write the invariant as a comment above the loop, and dry-run the first and the last rows, where off-by-one errors live.

Interview questions

Why is the converging pair search on a sorted list O(n), not O(n²)? (warm-up)

Every step computes one sum and then moves one pointer inward, so hi − lo, which starts at n − 1, falls by one each step: at most n − 1 sums in all. The search is linear because each move rules out many pairs at once. When the sum is too small, the smaller value cannot reach the target with any partner left, because its largest possible partner has just failed, so every pair that uses it is ruled out; a sum that is too large rules out every pair that uses the larger value. The sorted order is what makes those eliminations valid. If the input is not sorted, sorting it first costs O(n log n), which then dominates the total.

What does the write pointer mean in an in-place compaction? (warm-up)

It is the length of the finished part of the list: items[:write] holds exactly the items kept so far, in their original order, and position write is where the next kept item goes. The reader moves every step and the writer only when an item is kept, so the writer is never ahead of the reader and never overwrites an item that has not been read. When the reader reaches the end, write is the new length: truncate the list there in Python, or return it as the length in a language whose arrays cannot shrink. The cost is one scan, O(n) time with O(1) extra memory.

Key takeaways

• Two pointers replace a nested loop when each move can rule out candidates for good, thanks to an order, a symmetry or an in-place job.
• Converging pointers start at both ends and move inward; reader–writer pointers both move right through one list; a parallel scan gives each of two sorted lists a pointer.
• Justify every move with the invariant. For pair sums: no pair that fits has i < lo or j > hi.
• The sorted pair search makes at most n − 1 sums where the brute force makes n(n − 1)/2: 199,999 against about 2 × 10¹⁰ at n = 200,000.
• In Java and C++, add two large ints in 64 bits. Java’s int wraps around without a word, and in C++ the overflow is undefined behaviour.