Two pointers & sliding window

Walk the array, don't re-scan it. A whole class of "is there a pair/subarray/substring with property P?" questions collapse from O(n²) to O(n) the moment you notice the feasibility is monotonic in one direction — then a pointer can advance and never back up.

Why this pattern

The brute-force way to answer "is there a pair/subarray/substring with property P?" is to try all O(n²) pairs or all O(n²) windows. But for a huge class of problems the array (or the window's feasibility) is monotonic in a way that lets a pointer move in ONE direction and never back up. When a pointer only ever advances, the total work across the whole run is O(n), not O(n²). That is the entire economic argument for both patterns: amortize the scan.

There are two flavours. They share one idea — coordinate two indices so the combined movement is linear — but differ in when you reach for them.

Opposite-ends two pointers

Mental model: a left pointer at the start, a right pointer at the end, walking toward each other. The trigger signal: the input is sorted (or you can sort it), and you are looking for a pair/partition where moving an end deterministically improves or worsens the objective.

Fast / slow pointers (read vs write)

Mental model: a "read" pointer scans every element; a "write" pointer marks the boundary of the cleaned-up region. Trigger: in-place compaction (remove dups / remove value / move zeroes) where you must keep O(1) extra space. Invariant: everything left of write is the finished answer.

Sliding window

Mental model: a window [left, right] over a contiguous run. Trigger signal — the problem says "subarray" or "substring" (contiguous!) AND the window's feasibility is monotonic: if a window is too big/invalid, shrinking it can only help; if it's valid, you want to push the other edge. That monotonicity is what makes the linear scan correct.

The general template for variable-size windows

left = 0
for right in range(n):
    include a[right] into the window state
    while the window VIOLATES the invariant:
        remove a[left] from the window state
        left += 1
    # here [left, right] is the largest valid window ending at right
    update answer

Each index is added once (right advances n times) and removed at most once (left advances <= n times) ⇒ O(n) total despite the nested while. The while is NOT O(n) per iteration; it's O(n) summed over the whole run (amortized).

Opposite-ends two pointers

LeetCode 167 — Two Sum II (input array is sorted)

Return 1-based indices of the two numbers adding to target. The array is sorted, so the sum a[lo]+a[hi] increases when we move lo right and decreases when we move hi left. We can steer the sum toward target deterministically and never need to revisit a discarded end.

def two_sum_sorted(a: List[int], target: int) -> List[int]:
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo + 1, hi + 1]
        if s < target:
            lo += 1          # need bigger sum: smallest element can't help anyone
        else:
            hi -= 1          # need smaller sum: largest element is too big
    return []                # problem guarantees a solution; defensive return

LeetCode 125 — Valid Palindrome

Consider only alphanumeric chars, ignore case. A palindrome reads the same from both ends, so compare the two ends and walk inward, skipping non-alphanumeric characters as we go.

def is_palindrome(s: str) -> bool:
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if not s[lo].isalnum():
            lo += 1
        elif not s[hi].isalnum():
            hi -= 1
        elif s[lo].lower() != s[hi].lower():
            return False
        else:
            lo += 1
            hi -= 1
    return True

LeetCode 11 — Container With Most Water

Area = (hi - lo) * min(height[lo], height[hi]). Start at the widest container. Width only shrinks as we move in, so the ONLY way to beat the current area is a taller wall. The shorter wall caps the area, and moving the shorter wall is the only move that can find a taller bound — moving the taller wall can never increase min(...) while width drops. So we always discard the shorter wall. This greedy is provably optimal because every pair we skip is dominated by one we keep.

def max_area(height: List[int]) -> int:
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(height[lo], height[hi]))
        if height[lo] < height[hi]:
            lo += 1          # shorter wall is the bottleneck; only it can improve
        else:
            hi -= 1
    return best

Reverse a list in place

The in-place mutation half of many problems: swap symmetric pairs from the outside in.

def reverse_in_place(a: List[int]) -> List[int]:
    lo, hi = 0, len(a) - 1
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1
    return a

LeetCode 75 — Sort Colors (Dutch National Flag)

Sort an array of 0s, 1s, 2s in one pass, in place. THREE pointers partition the array into four regions:

The invariant holds at every step. We inspect a[mid]:

• 0: swap into the 0-region; both low & mid advance (the swapped-in value came from the 1-region so it's a known 1, safe to step over).
• 1: already in place, just advance mid.
• 2: swap into the 2-region; do NOT advance mid because the swapped-in value is still unknown and must be re-examined.

def sort_colors(a: List[int]) -> List[int]:
    low, mid, high = 0, 0, len(a) - 1
    while mid <= high:
        if a[mid] == 0:
            a[low], a[mid] = a[mid], a[low]
            low += 1
            mid += 1
        elif a[mid] == 1:
            mid += 1
        else:  # a[mid] == 2
            a[mid], a[high] = a[high], a[mid]
            high -= 1   # mid stays put: re-inspect the value we just pulled in
    return a

Fast / slow pointers (read vs write compaction)

LeetCode 26 — Remove Duplicates from Sorted Array

Compact in place; return the new logical length k, where a[:k] holds the uniques. write marks the end of the deduped prefix; read scans ahead. Because the array is sorted, a duplicate is always equal to a[write-1], so a single comparison detects novelty. Only copy when the value is new.

def remove_duplicates_sorted(a: List[int]) -> int:
    if not a:
        return 0
    write = 1  # first element is always kept
    for read in range(1, len(a)):
        if a[read] != a[write - 1]:
            a[write] = a[read]
            write += 1
    return write

Sliding window — fixed size

Maximum sum of any contiguous subarray of size k

Instead of recomputing each window's sum (O(nk)), slide it: add the entering element, subtract the leaving one. The window size is fixed so there's no shrink loop — just a rolling sum.

def max_sum_subarray_k(a: List[int], k: int) -> int:
    if k <= 0 or k > len(a):
        raise ValueError("k must be in 1..len(a)")
    window = sum(a[:k])
    best = window
    for right in range(k, len(a)):
        window += a[right] - a[right - k]  # slide by one: +new, -old
        best = max(best, window)
    return best

Sliding window — variable size (the template in action)

LeetCode 3 — Longest Substring Without Repeating Characters

Invariant = the window contains no duplicate. Expand right; if the new char is already inside, shrink from the left until it's gone. Every char enters and leaves at most once ⇒ O(n). The window is always the longest valid one ending at right, so tracking its max length suffices.

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:                  # invariant violated: duplicate present
            seen.discard(s[left])          # remove leftmost until ch is unique
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

LeetCode 340 — Longest Substring with At Most K Distinct Characters

Invariant = window holds <= k distinct chars. Keep a count map of chars in the window. Expand right; while distinct-count exceeds k, drop the leftmost char (decrement its count, evict when it hits 0). This is the exact template, just with len(count) <= k as the feasibility predicate.

def longest_k_distinct(s: str, k: int) -> int:
    if k <= 0:
        return 0
    count = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > k:              # too many distinct: shrink
            left_ch = s[left]
            count[left_ch] -= 1
            if count[left_ch] == 0:
                del count[left_ch]
            left += 1
        best = max(best, right - left + 1)
    return best

LeetCode 76 — Minimum Window Substring (the hardest variant)

Smallest substring of s containing every char of t (with multiplicity). This is the dual of "longest": here we want the SMALLEST valid window, so we expand right until the window becomes VALID (covers all of t), then shrink left as far as possible while STILL valid, recording the best. need counts required chars; missing tracks how many requirements are unmet. A char only reduces missing when it covers a still-needed requirement (need[ch] > 0 at the moment we consume it) — that's the subtle bookkeeping.

def min_window_substring(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    missing = len(t)             # total still-unmet character demand
    left = 0
    best_len = len(s) + 1
    best_l = 0
    for right, ch in enumerate(s):
        if need.get(ch, 0) > 0:  # this char fulfils an outstanding requirement
            missing -= 1
        need[ch] = need.get(ch, 0) - 1   # window now "owns" one ch
        while missing == 0:              # valid: try to shrink from the left
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l = left
            need[s[left]] += 1           # give back the leftmost char
            if need[s[left]] > 0:        # we now lack it again -> invalid
                missing += 1
            left += 1
    return "" if best_len == len(s) + 1 else s[best_l:best_l + best_len]

A quick sanity check on the headline cases: min_window_substring("ADOBECODEBANC", "ABC") returns "BANC", length_of_longest_substring("pwwkew") returns 3 (the window "wke"), and sort_colors([2,0,2,1,1,0]) sorts to [0,0,1,1,2,2] in a single pass.