Opposite ends, then the list, then the walls

Opposite-direction two-sum on a sorted array

Recognize it from

Array is sorted (or you may sort). Find two indices whose values sum to a target. Pair, not a subarray of length ≥ 3. Three-sum is this loop inside an outer index. If they forbid reordering and the array is unsorted, use a HashMap of complements instead.

What it actually does

lo starts at 0, hi at n − 1. The sum a[lo] + a[hi] is monotone in both pointers: too small means every remaining pair that still uses lo needs a larger partner, so lo++; too large means hi--. Each index moves at most once.

That argument needs sorted order. After a sort, original indices are lost unless you stored (value, index) pairs. Overflow: add in long in the interview block.

public boolean twoSumSorted(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) return true;
        // sorted: a larger left partner is the only way to grow the sum
        if (s < target) lo++;
        else hi--;
    }
    return false;
}

public int[] twoSumSorted(int[] a, int target) {
    if (a == null || a.length < 2) return new int[]{-1, -1};
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        long s = (long) a[lo] + a[hi]; // int+int can overflow past a 1e9 target
        if (s == target) return new int[]{lo, hi};
        if (s < target) lo++;
        else hi--;
    }
    return new int[]{-1, -1};
}

Example 1 — simple

Input a = [1, 2, 4], target = 6.

Answer true / indices [1, 2].

Example 2 — every step

Input a = [1, 2, 3, 4, 6], target = 10. Every lo/hi move, none skipped.

Answer indices [3, 4]. If the target were 11, the last step would be lo == hi after hi-- from a too-large 4+6, and you would return [-1, -1].

Notebook problems for this topic

Fast / slow cycle detection

Recognize it from

Linked list, “does it loop,” “start of the cycle,” “happy number” (the tortoise on a function graph). Not a cycle in an explicit node-graph — that is DFS 3-state or Union-Find in the graphs chapter.

What it actually does

Slow walks one node, fast walks two. If there is no cycle, fast hits null. If there is a cycle, fast laps slow and they meet inside the cycle. That is phase 1. The simple method stops there and returns a boolean.

Phase 2 (interview): put one pointer back at the head and walk both one step at a time. They meet at the cycle entrance. Why: if the stem has length μ and they first met after the slow pointer had walked μ+a steps, the remaining distance around the cycle lines up so the head and the meet-point are equally far from the entrance. You do not need to prove it in Live Code — you do need to type the second walk and not forget fast.next.next null-checks.

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;           // one hop
        fast = fast.next.next;      // two hops; null-check is the no-cycle exit
        if (slow == fast) return true;
    }
    return false;
}

public ListNode detectCycle(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    boolean met = false;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) { met = true; break; }
    }
    if (!met) return null;
    // phase 2: head and meet-point are equally far from the cycle start
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

Example 1 — simple

List 1 → 2 → 3 → 2 (3 points back at 2). Cycle of two nodes.

Answer true. Interview phase 2 from this meet: reset slow to 1, fast stays at 3. One step: slow=2, fast=2. Cycle start is 2.

Example 2 — every step

List 1 → 2 → 3 → 4 → 5 → 3. Meet point, then the start-of-cycle walk.

Answer: cycle starts at node 3. Simple hasCycle would have returned true at the meet on move 3 and stopped.

Notebook problems for this topic

Trapping rain water — two pointers

Recognize it from

Bars on a line, water sits in valleys. Water at index i is min(leftMax, rightMax) − h[i] if that is positive. Container-with-most-water is the sibling (area between two bars, not water on bars). This card is trapping.

What it actually does

The simple method precomputes, for every i, the tallest bar to the left and to the right (including i). Then one pass adds min(L[i], R[i]) − h[i]. That is O(n) time and O(n) extra arrays.

The interview method keeps two pointers and running maxL / maxR. The smaller wall decides the water at that pointer: if h[left] ≤ h[right], the left bar’s water cannot exceed maxL, because there is already a right wall at least as tall as h[left]. Update maxL or add water, then move left. Symmetric on the right. O(1) extra memory.

public int trap(int[] h) {
    int n = h.length;
    if (n == 0) return 0;
    int[] leftMax = new int[n], rightMax = new int[n];
    leftMax[0] = h[0];
    for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], h[i]);
    rightMax[n - 1] = h[n - 1];
    for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], h[i]);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        // valley depth = shorter bounding wall minus this bar
        ans += Math.min(leftMax[i], rightMax[i]) - h[i];
    }
    return ans;
}

public int trap(int[] h) {
    if (h == null || h.length == 0) return 0;
    int left = 0, right = h.length - 1;
    int maxL = 0, maxR = 0, ans = 0;
    while (left < right) {
        if (h[left] <= h[right]) {
            // right is already a wall ≥ this bar, so left water is bounded by maxL
            if (h[left] >= maxL) maxL = h[left];
            else ans += maxL - h[left];
            left++;
        } else {
            if (h[right] >= maxR) maxR = h[right];
            else ans += maxR - h[right];
            right--;
        }
    }
    return ans;
}

Example 1 — simple

Input h = [0, 1, 0, 2]. Four bars, one unit of water.

Answer 1.

Example 2 — every step

Input h = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] — the classic 12-bar, every pointer move, no bar skipped.

Answer 6. Bar 5 (height 0) is the 2-unit puddle between the 2-wall and the 3-wall; the last unit sits at index 9.

Notebook problems for this topic

Celebrity elimination

Recognize it from

A celebrity is known by everyone and knows no one. API knows(a, b) or a 0/1 matrix. Ask: none possible (−1)? n=1? directed “follows”? Variants stay unnamed — confirm classic before you type this elimination.

What it actually does

Brute: for each candidate, scan the whole row (knows nobody) and column (everybody knows them). O(n²) calls.

Interview: one candidate. For i from 1 to n−1, if knows(cand, i) then cand is not a celebrity, so cand = i; else i is not. One person remains. Then verify in O(n): cand knows nobody, everybody else knows cand. Skip verify and you ship a false celebrity. Two-pointer form is the same idea: if A knows B, A dies, else B dies.

public int findCelebrity(int n) {
    for (int cand = 0; cand < n; cand++) {
        boolean ok = true;
        for (int i = 0; i < n; i++) {
            if (i == cand) continue;
            // celebrity knows nobody, and everybody knows celebrity
            if (knows(cand, i) || !knows(i, cand)) { ok = false; break; }
        }
        if (ok) return cand;
    }
    return -1;
}

public int findCelebrity(int n) {
    if (n <= 0) return -1;
    int cand = 0;
    for (int i = 1; i < n; i++) {
        // if cand knows i, cand is not the sink; else i is not
        if (knows(cand, i)) cand = i;
    }
    for (int i = 0; i < n; i++) {
        if (i == cand) continue;
        if (knows(cand, i) || !knows(i, cand)) return -1;
    }
    return cand;
}

boolean knows(int a, int b) { return false; // interviewer oracle }

Example 1 — simple

n=3, person 1 is known by everyone and knows no one.

Answer 1.

Example 2 — every step

n=3, no celebrity. Elimination still picks someone; verify fails.

Answer −1. Person 1 survived elimination and still knows 0. Skipping verify would have returned 1.

Notebook problems for this topic

See also on this chapter

Max-sum switching lists is two pointers on two sorted lists, not opposite-ends on one array — linked from the two-sum card. Rain-stocks on chapter 24 is rain plus a stocks DP; only the rain half is this chapter. tp-tri’s array problem is UNNAMED: lock the invariant, then this opposite-ends loop if they confirmed sorted pair-sum.