Two Pointers and Sliding Window

TL;DR: Two related tricks turn O(n^2) array scans into O(n). Converging pointers start at both ends of a sorted array and move inward, using the sorted order to decide which side to advance, which solves pair-finding without a nested loop. The sliding window keeps two pointers moving the same direction, expanding the right edge to grow a range and contracting the left edge to restore a constraint, maintaining a running invariant (a sum, a count, a set of seen characters) so each element is touched at most twice.

Converging pointers on sorted data

If an array is sorted, you can find a pair summing to a target without hashing or nesting. Put one pointer at the start, one at the end, and look at their sum. Too small, move the left pointer right (the only way to increase). Too big, move the right pointer left. Each step eliminates one candidate, so the whole search is O(n) after the sort.

def pair_sum_sorted(nums, target):     # nums is sorted ascending
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1                    # need a larger sum
        else:
            hi -= 1                    # need a smaller sum
    return []

The correctness argument is the part interviewers want: when s < target, no pair using the current nums[lo] and any smaller right value can reach the target, so lo can never be the answer with the current hi or anything left of it. Advancing lo discards exactly the pairs that cannot work. This is the same machinery behind reversing in place, partitioning, and the "remove duplicates from sorted array" family.

The expand-contract window

A sliding window handles "find the longest/shortest/best contiguous range satisfying a condition." Both pointers move right. The right edge expands the window and updates a running state; whenever the state violates the constraint, the left edge contracts until the constraint holds again. Because each pointer only moves forward and never resets, the total work is O(n) even though the window size varies.

def longest_unique_substring(s):
    seen = {}                          # char -> last index
    left = best = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1         # contract past the duplicate
        seen[c] = right
        best = max(best, right - left + 1)
    return best

Note the window carries a hash map of seen characters: the two techniques compose. The invariant here is "the window [left, right] contains no repeated character," and the running state is the position map that lets us jump left forward in O(1) instead of re-scanning.

Why it stays O(n)

The key insight: each pointer makes at most n forward moves over the whole run, so the total is at most 2n pointer advances, hence O(n). A nested loop would re-examine the prefix for every right position, giving O(n^2). The window amortizes that away because contracting never re-walks ground the left pointer already passed.

When each applies

Triple-sum (3-sum) combines both: sort, fix one element, then run converging pointers on the rest, which is O(n^2) overall and beats the O(n^3) triple loop.

Why interviewers probe this

These techniques screen for the instinct to replace nested iteration with a single coordinated pass. The strong-answer move is to name the invariant the window maintains and argue why each element is visited a bounded number of times, not just to produce working code. The held-back follow-up is often "prove it is O(n)" or "what is the invariant when you contract?" Candidates who coded by trial and error stumble here; the ones who reasoned about the invariant answer immediately. A second common follow-up: "does this still work if the array is not sorted?" (for converging pointers, no, which is why you sort first or switch to a hash map).

Common misconceptions

• "Sliding window is O(n^2) because of the inner while loop." The left pointer moves at most n times total across the whole run, so it amortizes to O(n), not O(n) per step.
• "Converging pointers work on any array." They rely on sorted order; on unsorted data you sort first or use a hash map.
• "You must recompute the window state from scratch each step." The point is to update incrementally: add the entering element, remove the leaving one.
• "Two pointers and sliding window are the same thing." Converging pointers move toward each other on sorted data; a window moves both pointers the same direction maintaining a contiguous range.

Key takeaways

• Converging pointers exploit sorted order to find pairs in O(n) after the sort, discarding impossible candidates each step.
• The sliding window expands on the right and contracts on the left to keep a running invariant, touching each element at most twice.
• Both replace an O(n^2) nested loop with a single O(n) pass; the win comes from never re-walking passed ground.
• State the invariant and the amortized bound out loud; that is what the O(n) claim rests on.