Two Pointers and Sliding Window

1Two indices instead of nested loops

Two-pointer techniques maintain two indices into a sequence and move them according to a rule — toward each other, or both forward at possibly different speeds. The goal is to solve pair, partition, or window problems in O(n) time instead of an O(n^2) double loop that re-checks the same pairs.

The method is not free magic: opposite-end pair search needs sorted order (or a sort that costs O(n \log n) first). Sliding windows need a constraint you can maintain by growing and shrinking a contiguous span. When those ingredients are present, each element is touched a constant number of times.

Figure. Two indices replace a nested scan when the array's order lets you advance exactly one side per step.

Why it beats O(n^2)

1. One pass familyPointers only advance (or only retreat); they never restart from the beginning for each i.
2. Amortized linearAcross the whole run, left and right each move at most n steps → O(n) total work.
3. SpaceOften O(1) extra — just the indices (plus a small frequency map for some windows).

2Opposite-end pointers on a sorted array

On a sorted array, place left at the start and right at the end. Compare the sum (or other monotone combination) to the target: if too small, advance left to increase the sum; if too large, move right leftward to decrease it; if equal, you have the pair. Each step discards one index permanently.

Unsorted data must be sorted first — O(n \log n) — or you switch to a hash map that spends O(n) extra memory. Opposite-end exploits sortedness specifically to keep extra memory at O(1).

Figure. Start with L on 1 and R on 11. Sums that are too large shrink R; sums that are too small advance L until 4 + 5 = 9.

Pair sum inward

1. Initializeleft = 0, right = n − 1 on a sorted array.
2. Compare sumIf nums[left] + nums[right] < target, left++; if greater, right−−; if equal, return the pair.
3. StopPointers meet ⇒ no pair. Total movements ≤ n.

3Sliding window: grow right, shrink left

A sliding window maintains a contiguous subarray or substring [\mathrm{left}, \mathrm{right}]. Expand by advancing right to include new elements; when a constraint breaks, advance left to drop elements from the front until the window is valid again. Track a best answer (length, sum, count) at each valid state.

Because left and right only move forward, each index enters and leaves the window at most once — total work O(n) even though a nested description sounds quadratic.

Figure. A contiguous window on "abcabcbb". Grow R to include; when a duplicate enters, advance L until the window is unique again.

Variable window skeleton

1. Expandright++ and update the window's summary (sum, set, counts).
2. Shrink while invalidWhile the constraint fails, remove s[left] from the summary and left++.
3. RecordUpdate the best answer from the current valid window, then continue expanding.

4Fixed-size vs variable-size windows

A fixed window of length k always covers k elements: slide by dropping the outgoing element and adding the incoming one, usually in O(1) work per step after the first window is built. Use it for "best subarray of length exactly k".

A variable window grows and shrinks to satisfy a predicate — longest substring with all unique characters, shortest subarray with sum at least S. The length is the answer (or part of it), not an input. Mixing the two usually means you hardcoded k on a problem that asked for an extremal length.

Same strip shape as Sliding window: grow right, shrink left — fixed windows hold length k; variable windows let length be the answer while the constraint holds.

5Longest substring without repeating characters

Maintain window [\mathrm{left}, \mathrm{right}] and a set (or last-seen map) of characters inside it. Advance right; if s[\mathrm{right}] is already in the window, advance left — removing characters as you go — until that character is unique again. After each expansion, the window length is a candidate maximum.

On s = \texttt{abcabcbb} the answer is 3 ("abc"). The run is O(n) because each pointer only moves forward.

Track the window on the Sliding window: grow right, shrink left strip: grow while characters are new, shrink from the left on a repeat, and keep the best length seen.

Shrink on duplicate

1. Expand rightInclude s[right] in the window structure.
2. RepairWhile s[right] duplicates a window character, drop s[left] and left++.
3. Track maxbest = max(best, right − left + 1).

Variable window with a set

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Coding lab. Longest unique window in abcabcbb runs in the app, with checks on your output.

6Fast and slow pointers

Fast/slow (Floyd) uses two pointers at different speeds on a linked structure: typically slow moves one step while fast moves two. If there is a cycle, fast eventually laps slow and they meet inside the loop. If fast hits null, there is no cycle.

The same idea finds a midpoint in one pass: when fast reaches the end, slow sits at the middle — useful before reversing the second half of a list. Speed difference, not sortedness, is the ingredient.

Figure. A→B→C→D→E with E linking back to C along the outside. Fast and slow start at A; they first meet at D in the ledger's three-tick walk.

Cycle detection

1. Start togetherslow = fast = head.
2. Advanceslow = slow.next; fast = fast.next.next (when safe).
3. DecideMeet ⇒ cycle. fast becomes null ⇒ acyclic.

7Why windows are amortized O(n)

Fixed windows of size k: build the first window in O(k), then each slide removes one element and adds one — O(1) per step, O(n) over the array. Variable windows: every index is assigned to right once and to left at most once, so expand/shrink work sums to O(n) even if an inner while-loop looks scary in isolation.

Opposite-end two pointers share the same accounting: left only increases, right only decreases, at most n moves total. Sorting first, when required, dominates at O(n \log n).

Figure. Amortized O(n): every index is enqueued at most once and dequeued at most once across the whole scan.

Charge each move once

1. Right advancesAt most n expansions.
2. Left advancesAt most n shrinks — left never retreats.
3. TotalO(n) updates of the window summary (plus O(n \log n) if you sorted first).

8Which pointer pattern fits

Sorted pair or container problems → opposite-end. Contiguous extremum under a constraint → sliding window (fixed if k is given, variable if length is the answer). Cycle or midpoint on a list → fast/slow. Unsorted pair sum with O(n) memory OK → hash map from the hashing topic instead.

If you catch yourself restarting a second index from 0 for every i, ask whether a monotonic pointer or window would let that index only move forward.

Pick from the pattern table: sorted pair sum → opposite-end; contiguous extremum under a constraint → sliding window; list cycle or midpoint → fast/slow; unsorted pair with O(n) memory → hash map.