Patterns: Two Pointers & Sliding Window

Two pointers on a sorted array

The [[two-pointers|two-pointers]] pattern keeps two indices into an array and moves them toward each other (or in tandem) based on what they find. The classic use: given a *sorted* array, find a pair that sums to a target. Brute force checks every pair — O(n²). Two pointers does it in O(n) by exploiting the sort.

Sorted:  [ 1   3   4   6   8   9 ]      target = 10
           L                   R
  1 + 9 = 10  -> found!  (too small? move L right; too big? move R left)

  e.g. target = 11:
           L               R          1 + 8 = 9  < 11  -> L++
               L           R          3 + 8 = 11 -> found!

L starts left, R starts right. If the sum is too small, the only way up is L++; if too big, the only way down is R--. Each step eliminates one possibility.

#include <vector>

bool hasPairSum(const std::vector<int>& a, int target) {
    int L = 0, R = (int)a.size() - 1;
    while (L < R) {
        int sum = a[L] + a[R];
        if (sum == target) return true;
        else if (sum < target) L++;   // need a bigger sum
        else R--;                     // need a smaller sum
    }
    return false;
}

One while-loop, both pointers advancing toward each other. The array is sorted, so each comparison rules out a whole row of pairs. O(n) time, O(1) extra space.

Fast and slow pointers

A second flavor moves two pointers at *different speeds* along the same sequence. Send a slow pointer one step at a time and a fast pointer two steps at a time. If the structure loops back on itself, the fast one eventually laps the slow one and they meet — that's the famous way to detect a cycle in a linked list, with no extra memory.

struct Node { int val; Node* next; };

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;          // +1 step
        fast = fast->next->next;    // +2 steps
        if (slow == fast) return true;   // they met: there's a cycle
    }
    return false;                   // fast reached the end: no cycle
}

If there's a loop, the +2 pointer keeps gaining on the +1 pointer until it laps it. If there's no loop, fast simply runs off the end. O(n) time, O(1) space.

The sliding window

When a problem asks about contiguous subarrays or substrings — "the longest run with no repeats," "the max sum of any 5 in a row" — the [[sliding-window|sliding window]] pattern shines. Picture a window framing a stretch of the array. Instead of recomputing each window from scratch, you *slide* it: add the new element on the right, drop the old one on the left, and update a running total. Each element enters and leaves the window once, so the whole sweep is O(n) instead of O(n²).

Array: [ 2  1  5  1  3  2 ]   find max sum of any 3 in a row (window k=3)

  [2  1  5] 1  3  2     sum = 8
   2 [1  5  1] 3  2     slide: -2 +1  -> 8 - 2 + 1 = 7
   2  1 [5  1  3] 2     slide: -1 +3  -> 7 - 1 + 3 = 9   <- best
   2  1  5 [1  3  2]    slide: -5 +2  -> 9 - 5 + 2 = 6
                                          answer = 9

Each slide is one subtraction + one addition — O(1) work — instead of re-summing k elements. The window glides across in a single pass.

#include <vector>

int maxSumWindow(const std::vector<int>& a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];   // first window
    int best = sum;
    for (int i = k; i < (int)a.size(); i++) {
        sum += a[i] - a[i - k];     // slide: add right, drop left
        best = std::max(best, sum);
    }
    return best;
}

A fixed-size window: compute the first window once, then each step is +new -old. Total work O(n).

Variable windows, and how to spot the pattern

Many windows aren't a fixed size — they *grow and shrink*. To find the longest substring with no repeated characters, you grow the window's right edge to include new characters, and whenever a repeat appears, you shrink the left edge until the repeat is gone. Both edges only ever move *rightward*, so even though there are two moving pointers, each visits every position at most once — still O(n) overall.

Notice what these patterns share with the rest of this rung: they all replace blind, repeated recomputation with a smarter sweep that *reuses* what it already knows — the running sum, the sorted order, the visited set. That instinct — "don't redo work I've already done" — is the thread running through greedy, DP, and these patterns alike. You now have a real toolbox; the next rung is about wielding it with confidence.