Two Pointers

In Arrays & Hashing you paid memory to buy speed. This pattern gets the same speed for free — if the data is sorted. Interviewers love it because it has a tell: candidates who memorized solutions move the pointers correctly but can’t explain why it’s safe to skip checking millions of pairs. This module makes you the candidate who can.

The Goal

By the end of this module you can:

• Explain the elimination logic — why moving one pointer safely discards a whole batch of pairs without checking them
• Recognize the three shapes: converging, fast/slow, and same-direction reader/writer
• Implement the Java template for each shape from memory
• Solve pair-sum on a sorted array in O(n) time and O(1) space
• Decide in 30 seconds when two pointers beats a hash map, and when it loses
• Rewrite an in-place array problem (remove duplicates, move zeroes) without allocating a second array

The Lesson

The core insight — sorted order lets you discard without checking

Brute-force pair search checks every pair: O(n²). Two pointers checks at most n pairs and still never misses the answer. That sounds like cheating. Here is exactly why it isn’t — and this is the heart of the module, so go slow.

Setup: a sorted array, pointer L at the start, pointer R at the end. You want arr[L] + arr[R] == target.

Say arr = {1, 3, 5, 8, 11} and target = 9. First check: arr[L] + arr[R] = 1 + 11 = 12. Too big. Now the key question — what did that one comparison just teach you?

The sum was too big with arr[L] = 1, the smallest element in the array. Every other candidate partner for arr[R] = 11 is bigger than 1 (the array is sorted, and they all sit to the right of L). So:

• 3 + 11? Bigger than 12. Too big.
• 5 + 11? Bigger still. Too big.
• 8 + 11? Too big.

Every pair ending at R that starts later than L is guaranteed too big — without computing a single one of them. The element at R cannot be part of any answer. It’s not “probably wrong,” it’s provably wrong. So you retire it: R--. One comparison just eliminated four pairs.

The mirror argument: if the sum is too small, then arr[L] paired with its largest available partner still fell short — so arr[L] paired with anything smaller fails harder. L is dead. L++.

flowchart TD
    A["compare arr L plus arr R to target"] --> B{"sum vs target"}
    B -->|"too big"| C["arr R fails even with the smallest partner left"]
    C --> D["every pair ending at R is dead, move R left"]
    B -->|"too small"| E["arr L fails even with the largest partner left"]
    E --> F["every pair starting at L is dead, move L right"]
    B -->|"equal"| G["answer found"]

Each comparison kills one pointer position — a whole row or column of the pair grid — so after at most n comparisons the pointers meet and you’ve implicitly ruled out all O(n²) pairs. This only works because the array is sorted. Unsorted, “too big” tells you nothing about the neighbours, and the whole proof collapses. Remember that — it decides when this pattern applies at all.

This discard-half-the-candidates-per-question energy should feel familiar soon: binary search is the same idea taken to its extreme.

Shape 1 — Converging (ends walk inward)

The shape from the proof above. Also powers Valid Palindrome: compare the outermost characters, walk inward.

public class PairSumSorted {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 8, 11};
        int target = 9;

        int L = 0, R = arr.length - 1;
        while (L < R) {
            int sum = arr[L] + arr[R];
            if (sum == target) {
                System.out.println("Found: " + arr[L] + " + " + arr[R]);
                return;
            } else if (sum > target) {
                R--;            // R is dead - proven above
            } else {
                L++;            // L is dead - mirror argument
            }
        }
        System.out.println("No pair");
    }
}

The loop condition is L < R, not <= — a pair needs two different elements. Off-by-one here is the classic slip.

The same converging skeleton checks a palindrome — compare the ends, walk inward, bail on the first mismatch:

public class Palindrome {
    public static void main(String[] args) {
        String s = "nitin";
        int L = 0, R = s.length() - 1;
        boolean ok = true;
        while (L < R) {
            if (s.charAt(L) != s.charAt(R)) { ok = false; break; }
            L++;
            R--;
        }
        System.out.println(ok);   // true
    }
}

Same shape, different question: here both pointers move each step, because a single mismatch kills the whole answer — no sum to steer by.

Shape 2 — Fast/slow (one pointer outruns the other)

Two pointers moving the same direction at different speeds. The famous use: detecting a cycle in a linked list — if a fast pointer (2 steps) and a slow pointer (1 step) ever meet, you’re running in a circle, like two runners on a track. That’s a teaser; the full version, with the why-they-must-meet proof, lives in linked lists.

On arrays, fast/slow appears as “find the middle in one pass”: when fast hits the end, slow is at the midpoint.

public class FindMiddle {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70};
        int slow = 0, fast = 0;
        while (fast < arr.length - 1 && fast + 1 < arr.length) {
            slow++;
            fast += 2;
        }
        System.out.println("Middle: " + arr[slow]);   // 40
    }
}

Shape 3 — Same-direction reader/writer (in-place editing)

The shape interviews disguise hardest. One pointer reads every element; the other writes only the elements that deserve to stay. Everything left of the writer is the clean, finished output — built inside the original array, zero extra space.

Remove duplicates from a sorted array:

public class RemoveDuplicates {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 2, 3, 4, 4};

        int write = 1;                            // arr[0] always survives
        for (int read = 1; read < arr.length; read++) {
            if (arr[read] != arr[write - 1]) {    // new value, not a repeat
                arr[write] = arr[read];
                write++;
            }
        }

        System.out.print("First " + write + " elements: ");
        for (int i = 0; i < write; i++) System.out.print(arr[i] + " ");
        // First 4 elements: 1 2 3 4
    }
}

Move Zeroes is the same skeleton with a different keep-rule: writer collects non-zeros, then the tail gets filled with zeros. Once you see reader/writer, half of the “in-place, O(1) space” problems become the same problem.

Two pointers vs hash map — the decision

This is the judgment interviewers actually probe:

The one-line summary: two pointers wins when the data is sorted (or sortable for free) and space is tight; the hash map wins when the data is unsorted and you can’t afford to sort.

Complexity — always show the win

Each pointer moves at most n times total and never moves backward — that’s the whole runtime argument. For n = 1,000,000: ~500 billion pair checks brute-force, at most ~1,000,000 pointer steps converging.

Traps and edge cases

• L < R vs L <= R — pairs need <; single-element checks (like palindrome with odd length) are naturally handled by < too, since the middle character matches itself.
• Forgetting the precondition. Two pointers on an unsorted array gives confident wrong answers, not errors. The compiler won’t save you; the proof above is the only guard.
• Moving the wrong pointer. Sum too big → move R (shrink the sum). Re-derive it from the elimination logic, never from memory.
• Duplicates in converging shape. Problems like 3Sum demand skipping repeated values after a match, or you emit duplicate answers.
• Reader/writer order. The writer must never overtake the reader — if your version can, you’re overwriting unread data.

See It Move

Watch L and R on a sorted array — the dimmed elements are pairs being eliminated without being checked.

Step through it and notice:

• Exactly one pointer moves per comparison — and it’s always forced, never a choice.
• When the sum is too big, count how many pairs died with that single R--.
• The pointers never back up. Total steps across the whole run ≤ n — that is the O(n).
• Run it to “no pair found” and watch the pointers meet: every possible pair was eliminated or checked, none skipped unsafely.

Spot The Pattern

That last row matters: a window IS two same-direction pointers with a rule for when each moves. Sliding window is this pattern’s cousin, and the next module.

Where It Runs In Real Life

The merge step of merge sort — and database merge joins. Two sorted halves, one pointer each, repeatedly take the smaller: that’s the merge in merge sort. Databases do the same trick at scale: when both tables are sorted on the join key, a merge join walks one pointer down each table and never looks back — joining millions of rows in one pass instead of nested loops.

Log-file timestamp alignment. On-call at 2 AM with the app log and the payment-gateway log, both sorted by time, hunting for what happened around one failed transaction: you advance two pointers through two sorted streams, interleaving by timestamp. Every log-aggregation tool that merges sorted sources runs this loop.

Deduplication of sorted exports. Nightly data dumps sorted by customer ID, with repeats: the reader/writer pass compacts them in one sweep with zero extra memory — exactly your RemoveDuplicates program, pointed at a file with crores of rows.

In-place compaction. Garbage collectors, storage engines, and array-backed buffers all periodically slide live data toward one end to squeeze out the gaps — a writer pointer collecting survivors while a reader scans. Same shape, measured in gigabytes.

Build This

You’re building SettlementMatcher — converging pair-search plus a reader/writer compactor — then merging two sorted feeds.

1. Create a folder settlement, and inside it SettlementMatcher.java:

import java.util.Arrays;

public class SettlementMatcher {

    public static void main(String[] args) {
        int[] credits = {120, 250, 400, 575, 800, 910};   // sorted, in rupees
        findPair(credits, 1025);
        findPair(credits, 999);

        int[] feed = {100, 100, 250, 250, 250, 400, 575};
        int kept = compact(feed);
        System.out.println("Compacted: "
                + Arrays.toString(Arrays.copyOf(feed, kept)));
    }

    // Shape 1: converging
    static void findPair(int[] arr, int target) {
        int L = 0, R = arr.length - 1;
        int checks = 0;
        while (L < R) {
            checks++;
            int sum = arr[L] + arr[R];
            if (sum == target) {
                System.out.println(arr[L] + " + " + arr[R] + " = " + target
                        + "  (checks: " + checks + ")");
                return;
            } else if (sum > target) {
                R--;
            } else {
                L++;
            }
        }
        System.out.println("No pair for " + target + "  (checks: " + checks + ")");
    }

    // Shape 3: reader/writer dedup, returns count of kept elements
    static int compact(int[] arr) {
        if (arr.length == 0) return 0;
        int write = 1;
        for (int read = 1; read < arr.length; read++) {
            if (arr[read] != arr[write - 1]) {
                arr[write] = arr[read];
                write++;
            }
        }
        return write;
    }
}

2. Compile and run:

javac SettlementMatcher.java
java SettlementMatcher

Note the checks count: for a 6-element array, never more than 5 — against 15 brute-force pairs.

3. Break it — violate the precondition. Shuffle credits to {800, 120, 575, 250, 910, 400} and call findPair(credits, 825). The pair 575 + 250 = 825 is right there in the array — and the program reports “No pair.” Trace it: the first sum is 800 + 400 = 1200, too big, so it retires 400… and keeps retiring from the right until the pointers meet, walking straight past the answer. No exception, no warning — a confident wrong answer. That silence is why the sorted precondition matters. Sort the array back.

4. Break it — writer overtakes. In compact, change the comparison to arr[read] != arr[read - 1] and feed it {1, 1, 1, 2, 1, 1} (note: not fully sorted). Trace what gets written. Lesson: the writer must compare against what it kept, not what it just read — and dedup-by-neighbour assumes sorted input too.

5. Extend it — merge two sorted feeds. Add static int[] merge(int[] a, int[] b): pointer i on a, j on b, repeatedly copy the smaller into a result array, then drain whichever has leftovers. Test with {100, 400, 800} and {250, 250, 910}. You’ve now hand-built the merge-join from the real-life section.

6. Extend it — count the pairs. Change findPair to count all pairs summing to target (advance both pointers on a match, mind the duplicates). This is the step-up that 3Sum builds on.

Problems To Solve

The rule: solve until you can write the template from memory. If stuck 25 minutes, read the approach, close it, re-solve from scratch.

Check Yourself

1. The sum at (L, R) is too big. State exactly which pairs are eliminated and the one-sentence proof.
2. Why does the elimination argument collapse on an unsorted array?
3. Why is the total runtime O(n) and not O(n²), given there are O(n²) possible pairs?
4. Name the three shapes and one problem each.
5. In reader/writer dedup, why compare arr[read] against arr[write - 1] and not arr[read - 1]?
6. Unsorted array, need indexes of the pair: why does sort-then-two-pointers fail twice over?
7. When does two pointers beat the hash map, in one sentence?
8. How is a sliding window related to two pointers?

Explain it out loud: To the empty chair: walk through pair-sum on {1, 3, 5, 8, 11} with target 9, and at every pointer move, finish the sentence “I don’t need to check those pairs because…” If you ever say “because that’s the algorithm,” stop — re-read the elimination section and start over.

Still Unclear?

Copy-paste any of these into Claude — built to deepen, not to solve:

Walk me through the proof that converging two pointers on a sorted array
never skips a valid pair. Then give me an unsorted array where the same
pointer moves give a wrong answer, and make me explain which step of the
proof broke. Don't write code.

Here is my reader/writer solution to Remove Duplicates: [paste yours].
Ask me questions until I can state the loop invariant — what is always
true about everything left of the write pointer — in one sentence.

Give me six one-line problems, mixed between hash map, converging two
pointers, reader/writer, and sliding window. I will answer with the
pattern and one sentence of why. Grade me and explain my misses.

Why AI Can’t Do This For You

AI will write a flawless two-pointer loop on request — the typing was never the skill. The skill is the 30-second read: seeing “sorted” and “O(1) space” in a problem statement and knowing the pointers apply, or seeing “unsorted” and “return indexes” and knowing they don’t. In an interview you get no prompt box, and “I’d ask AI” is not an accepted complexity analysis.

On the job, the pattern hides deeper: a reconciliation script doing nested loops over two exports that are already sorted by transaction ID, melting the CPU for hours when one merge pass would finish in seconds. AI can’t spot that, because nobody asks it to — nobody knew the question existed. The engineer who carries the elimination logic in their head sees it in the code review. That’s the job.

Module done? Add it to today’s tracker