Two pointers and sliding window

Two patterns, one idea: most nested loops over a sequence do not need to be nested. Recognising when is worth more than any individual algorithm, because it turns O(n²) into O(n) in about the same number of lines.

#Two pointers

Find two numbers in a sorted array that add to a target. The obvious way tries every pair:

for (int i = 0; i < xs.length; i++)
    for (int j = i+1; j < xs.length; j++)
        if (xs[i] + xs[j] == target) return new int[]{xs[i], xs[j]};

The other way starts at both ends and walks inward. If the sum is too small, the only way to increase it is to move the left pointer right; if too large, move the right pointer left:

int lo = 0, hi = xs.length - 1;
while (lo < hi) {
    int sum = xs[lo] + xs[hi];
    if (sum == target) return new int[]{xs[lo], xs[hi]};
    if (sum < target) lo++; else hi--;
}

Forty thousand elements, and the only matching pair is the last two:

###   nested loops  [79996, 79998]      165 ms
###   two pointers  [79996, 79998]        1 ms

Same answer, 165 times. Each pointer moves at most n times, so the whole thing is one pass.

The precondition is sorted, and it is what makes the reasoning valid: knowing the array is ordered is what tells you which pointer to move. On unsorted data this pattern is wrong, and the answer is a HashSet of what you have seen — O(n) and no sorting.

#Sliding window

The same idea where the answer is a contiguous run rather than a pair.

The nested-loop version recomputes the sum of every window from scratch, which is the waste:

for (int i = 0; i <= n-k; i++) {
    int sum = 0;
    for (int j = i; j < i+k; j++) sum += xs[j];   // recomputes k additions every time
}

The window version moves the sum instead of rebuilding it — add the element entering, subtract the one leaving:

int sum = 0;
for (int i = 0; i < k; i++) sum += xs[i];
int best = sum;
for (int i = k; i < n; i++) {
    sum += xs[i] - xs[i-k];
    best = Math.max(best, sum);
}

O(nk) becomes O(n), and nothing about the code got harder to read.

Variable-size windows are the harder half, and the shape is always the same: grow the window from the right, and shrink from the left while the window is invalid.

int lo = 0, best = 0;
Set<Character> inWindow = new HashSet<>();
for (int hi = 0; hi < s.length(); hi++) {
    while (!inWindow.add(s.charAt(hi))) inWindow.remove(s.charAt(lo++));
    best = Math.max(best, hi - lo + 1);
}

That is "the longest substring with no repeated character", and the thing to notice is that lo only ever moves forwards. Both pointers together move at most 2n times, which is why a loop with a while inside it is still O(n) — a fact that looks wrong until you count the total movement rather than the nesting.

#Recognising the shape

The patterns apply when the answer is a pair or a run, and the sequence has an order you can exploit:

And when they do not apply: when the elements you need are not adjacent and the order gives you nothing. "Any two numbers summing to a target, unsorted" is a hash set. "The k largest" is a heap. Reaching for a window because the input is an array is how you get a wrong answer quickly.