When can you replace a nested loop with two pointers, and why is it correct?

The Answer

• Two pointers works when one comparison eliminates a candidate, not just a pair. That is the whole precondition.
• On a sorted array searching for a pair summing to a target: if the sum is too small, no pair using the current left element can reach the target — because the right element is already the largest available. So the left pointer moves on permanently.
• Each pointer only ever moves one way, so the total work is at most n steps: O(n) instead of O(n²).
• Sortedness is what licenses the deduction. On unsorted data a small sum tells you nothing, and the technique is simply wrong.
• A sliding window is the same idea for contiguous ranges: grow the right edge, and move the left edge forward only when the window becomes invalid.
• The giveaway that it applies: you are looking for a pair or a range, and the data is sorted or the validity condition is monotonic.

Understand It

The deduction that makes it correct

The loop everyone writes first compares every pair:

for i in 0..n:
    for j in i+1..n:
        if a[i] + a[j] == target: found      # n²/2 comparisons

Each comparison rules out exactly one pair. Two pointers rules out a whole row:

lo ← 0;  hi ← n - 1                  # requires a SORTED array

while lo < hi:
    sum ← a[lo] + a[hi]

    if sum == target: found
    if sum < target:  lo ← lo + 1     # a[hi] is the largest left; if it is
                                      #   not enough for a[lo], nothing is.
                                      #   Discard a[lo] entirely.
    else:             hi ← hi - 1      # symmetric: a[lo] is the smallest left,
                                      #   so a[hi] is too big for anything

Read the comment on the sum < target branch again, because it is the entire justification. We are not skipping a pair; we are proving that no pair containing a[lo] can work, because it has already been tested against the largest partner available. That is a statement about n/2 pairs, established by one addition.

The cost of that reasoning is the precondition: it is only true if a[hi] is really the largest remaining value. Sorted.

The difference, counted

for (int n : new int[] {1000, 2000, 4000}) {
    int[] a = evens(n);
    int target = a[n - 2] + a[n - 1];          // the last pair: worst case for brute force

    twoSumBrute(a, target);
    long brute = ops;
    twoSumPointers(a, target);
    long pointers = ops;

    System.out.printf("n=%-5d brute force: %,10d comparisons   two pointers: %,5d%n",
        n, brute, pointers);
}

n=1000  brute force:    499,500 comparisons   two pointers:   999
n=2000  brute force:  1,999,000 comparisons   two pointers: 1,999
n=4000  brute force:  7,998,000 comparisons   two pointers: 3,999

Double n: the brute force quadruples, the two-pointer version doubles. And look at the two-pointer numbers — n - 1 exactly. Every iteration moves one pointer one step, the pointers start n - 1 apart, and they meet. There is no slack in it.

Why each pointer must move only one way

That monotonicity is the proof of the O(n) bound, and it is also the thing people accidentally break. If any branch moved lo backwards, the loop could revisit pairs and the argument collapses — both the correctness argument (a discarded element was proven useless) and the complexity one.

So when writing a two-pointer loop, the check is: does every branch advance exactly one pointer, in its one permitted direction? If a case needs to move a pointer back, the problem is not a two-pointer problem.

Sliding window: the same idea for ranges

When the answer is a contiguous range rather than a pair, both pointers move the same direction and the invariant is about the window's contents:

start ← 0
for end in 0..n:                     # the window is a[start..end]
    include a[end]

    while window is invalid:          # shrink from the left until it is valid
        exclude a[start]
        start ← start + 1

    best ← max(best, end - start + 1)

It looks like a nested loop and is not: start never decreases, so across the whole run each index is entered once by end and left once by start. At most 2n moves, however much the inner while spins on any single iteration.

for (String s : new String[] {"abcabcbb", "bbbbb", "pwwkew", "abcdef"}) {
    int answer = longestUnique(s);
    System.out.printf("%-10s longest unique run = %d   (characters visited: %d)%n",
        "\"" + s + "\"", answer, ops);
}

"abcabcbb" longest unique run = 3   (characters visited: 8)
"bbbbb"    longest unique run = 1   (characters visited: 5)
"pwwkew"   longest unique run = 3   (characters visited: 6)
"abcdef"   longest unique run = 6   (characters visited: 6)

The visit count equals the string length every time, including "bbbbb" where the window collapses on every character. One pass, no matter how much the left edge has to catch up.

Reference

The three shapes, and when each applies:

// 1. Converging — a pair in a SORTED array
int lo = 0, hi = a.length - 1;
while (lo < hi) {
    int sum = a[lo] + a[hi];
    if (sum == target) return new int[] { lo, hi };
    if (sum < target) lo++; else hi--;
}

// 2. Same direction, fast and slow — cycle detection, or dedupe in place
int write = 0;
for (int read = 0; read < a.length; read++)
    if (read == 0 || a[read] != a[read - 1])
        a[write++] = a[read];            // removes duplicates from a sorted array
                                         // in O(n) with no extra memory

// 3. Sliding window — a contiguous range satisfying a monotonic condition
int start = 0;
for (int end = 0; end < a.length; end++) {
    include(a[end]);
    while (!valid()) exclude(a[start++]);
    best = Math.max(best, end - start + 1);
}

Does it apply? The checklist:

That last row is the one that quietly breaks. "Longest subarray with sum ≤ k" is a window problem only for non-negative numbers: with negatives, adding an element can make an invalid window valid again, so the left edge would need to move backwards. Use a prefix-sum map instead.

When sorting first is worth it:

// Unsorted input, and you need the VALUES not the original indices:
Arrays.sort(a);                     // O(n log n), then O(n) — beats O(n²)

// Unsorted input, and you need the ORIGINAL indices: sorting destroys them.
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < a.length; i++) {
    Integer j = seen.get(target - a[i]);
    if (j != null) return new int[] { j, i };
    seen.put(a[i], i);              // O(n) time, O(n) space, order preserved
}

Scenarios

Merging two sorted result sets. One pointer per list, advance whichever holds the smaller value. This is the merge step of merge sort, and it is why merging sorted data is O(n + m) rather than O(n log n) — no comparison is ever repeated.

Removing duplicates from a sorted array without allocating. The fast/slow form: read scans, write trails behind placing keepers. O(n) time, O(1) extra space, and the array is compacted in place. The same pattern is how ArrayList.removeIf avoids shifting repeatedly.

Rate limiting over a rolling minute. A queue of timestamps with the left edge dropping anything older than 60 seconds. A genuine sliding window, and monotonic because time only moves forward.

Where it does not apply: "longest subarray with sum exactly k" on data with negatives. Adding an element can move the sum back toward the target, so validity is not monotonic and the left edge cannot be advanced safely. Prefix sums with a hash map handle it in O(n); a window silently returns the wrong answer.

Interviewer's Next Move

1. "Why does the array have to be sorted?" Because the deduction depends on a[hi] being the largest remaining value. If it is, then a sum that is too small proves nothing containing a[lo] can reach the target, and a[lo] can be discarded. Unsorted, a small sum tells you nothing about any other pair, so there is no justification for advancing.

2. "Sorting is O(n log n) — hasn't that eaten the gain?" It has changed O(n²) to O(n log n), which is still a large win; and if the array arrives sorted, or you make several queries against it, the sort is paid once. But sorting destroys original indices, so if the answer must be indices into the input, a hash map at O(n) is the better trade.

3. "The inner while in a sliding window looks like a nested loop. Why is it O(n)?" Because start never moves backwards. Across the entire run it advances at most n times in total, no matter how those moves are distributed between iterations. Amortised over the loop, each element is included once and excluded once.

4. "When is a window not the right tool?" When validity is not monotonic — when adding an element can turn an invalid window valid. Sums with negative numbers are the standard example. The window assumes that once you must shrink, growing further will not help.

5. "Two pointers or binary search?" Both exploit sortedness, and they answer different shapes. Binary search finds one element in O(log n). Two pointers examines a relationship between two positions in O(n). Searching for each of n elements with binary search is O(n log n), which is worse than one two-pointer pass.

Check Yourself

Why can the left pointer be advanced permanently rather than just skipping that pair? Because it was compared against the largest remaining value. If even that partner gives too small a sum, every smaller partner does too — so no pair containing that element can succeed, and it is eliminated, not deferred.

A two-pointer pass on 4,000 elements used 3,999 comparisons. Why exactly that? The pointers start 3,999 apart and each iteration closes the gap by exactly one, until they meet. The bound is not approximate — it is n - 1 in the worst case, with no repeated work.

"Longest subarray with sum ≤ k." Is that a sliding window? Only if the values are non-negative. Then adding an element can never reduce the sum, so validity is monotonic and shrinking from the left is sufficient. With negatives, an invalid window can become valid by growing, and the window approach gives a wrong answer.