Two Pointers — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Coding Challenge — Container With Most Water¶

Problem. Given an integer array heights of length n, where heights[i] is the height of a vertical line at index i, find two lines that, together with the x-axis, form a container holding the most water. Return the maximum amount of water it can store.

Formally, maximize min(heights[i], heights[j]) * (j - i) over all 0 <= i < j < n.

Approach. Converging two pointers. At every step, the area is min(h[l], h[r]) * (r - l). Moving the taller wall inward shrinks the width without raising the height bound — area can only go down. So we must move the shorter wall inward. Track the maximum area seen.

Time: O(n). Space: O(1).

Invariant. The optimum (l*, r*) satisfies l <= l* < r* <= r. Justification: when h[l] < h[r], every pair (l, k) for k < r has width k - l < r - l AND bounded height <= h[l], so its area <= h[l] * (r - l), which is the current area we just considered. So l cannot be part of a strictly-better answer; discarding it is safe.

Go¶

package main

import "fmt"

// MaxArea returns the largest area of a container formed by two of the
// vertical lines in heights.
// Time: O(n). Space: O(1).
func MaxArea(heights []int) int {
    l, r := 0, len(heights)-1
    best := 0
    for l < r {
        width := r - l
        var h int
        if heights[l] < heights[r] {
            h = heights[l]
            l++ // discard the shorter wall
        } else {
            h = heights[r]
            r--
        }
        if area := width * h; area > best {
            best = area
        }
    }
    return best
}

func main() {
    fmt.Println(MaxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7})) // 49
    fmt.Println(MaxArea([]int{1, 1}))                       // 1
    fmt.Println(MaxArea([]int{4, 3, 2, 1, 4}))              // 16
}

Java¶

public class Solution {

    /**
     * Largest area of a container formed by two of the vertical lines.
     * Time: O(n). Space: O(1).
     */
    public static int maxArea(int[] heights) {
        int l = 0, r = heights.length - 1;
        int best = 0;
        while (l < r) {
            int width = r - l;
            int h;
            if (heights[l] < heights[r]) {
                h = heights[l];
                l++; // discard the shorter wall
            } else {
                h = heights[r];
                r--;
            }
            int area = width * h;
            if (area > best) best = area;
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
        System.out.println(maxArea(new int[]{1, 1}));                      // 1
        System.out.println(maxArea(new int[]{4, 3, 2, 1, 4}));             // 16
    }
}

Python¶

def max_area(heights: list[int]) -> int:
    """
    Largest area of a container formed by two of the vertical lines.
    Time: O(n). Space: O(1).
    """
    l, r = 0, len(heights) - 1
    best = 0
    while l < r:
        width = r - l
        if heights[l] < heights[r]:
            h = heights[l]
            l += 1   # discard the shorter wall
        else:
            h = heights[r]
            r -= 1
        area = width * h
        if area > best:
            best = area
    return best


if __name__ == "__main__":
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
    print(max_area([1, 1]))                       # 1
    print(max_area([4, 3, 2, 1, 4]))              # 16

Edge Cases the Interviewer Will Probe¶

Follow-Ups the Interviewer May Ask¶

1. What if you have to return the indices, not just the area? Track (best, best_l, best_r) together.
2. What if n is huge and the array is streamed? You cannot use converging pointers (no random access from the right). You would need O(n) extra memory to buffer, or accept an approximate answer.
3. Can you parallelize this? The data dependency chain makes the converging variant un-parallelizable; you would split the array into chunks, find the best within each, then combine (which is incorrect because the optimum pair can span chunks). A correct parallel version requires more care.
4. What is the relation to "trapping rain water"? Same input format, different output. Trapping rain water also has a two-pointer solution (move the side with the smaller max-so-far) and an alternative monotonic-stack solution (see topic 13).
5. Could you do it with a stack or DP instead? Yes, but both are O(n) space and conceptually heavier. Two pointers is the textbook answer because it is O(1) space.

The interviewer is checking that you can name the greedy invariant ("move the shorter side"), justify why it preserves the optimum, write the loop cleanly, and identify the edge cases without prompting.