Two Pointers & Sliding Windows

Two pointers and sliding windows

When a sorted array pairs up (or a contiguous run must satisfy a property), two indices moving inward/forward replace nested loops:

// pair summing to target in a sorted array — O(n) not O(n²)
int lo = 0, hi = xs.length - 1;
while (lo < hi) {
    int s = xs[lo] + xs[hi];
    if (s == target) return true;
    if (s < target) lo++; else hi--;
}

The sliding window maintains a running aggregate while advancing two co-moving boundaries:

// longest run with at most k distinct values
int left = 0, best = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int right = 0; right < xs.length; right++) {
    freq.merge(xs[right], 1, Integer::sum);
    while (freq.size() > k) {
        if (freq.merge(xs[left], -1, Integer::sum) == 0) freq.remove(xs[left]);
        left++;
    }
    best = Math.max(best, right - left + 1);
}

The key insight: each element enters and leaves the window at most once, so the while inside the for still totals O(n).