Two Pointers & Sliding Window

Most array problems feel like they need a nested loop: for every element, scan all the others. That works — but it is O(n²), and on a million-element array that is a trillion operations.

Two pointers and the sliding window fix this by keeping one or two indices that only ever move forward through the array. Because each element is visited at most twice (once by each pointer), the total work is O(n) regardless of how many “inner” iterations the loop appears to do.

The core intuition

Imagine reading a book. A brute-force approach re-reads every previous page before turning to the next one. Two pointers are like having two bookmarks: you advance them based on what you already know, never flipping back unnecessarily.

The key invariant: if you can prove neither pointer ever moves backward, you get O(n) for free.

Two pointers: sorted pair-sum

Given a sorted array and a target, find two indices whose values sum to the target.

Brute force: try every pair → O(n²).

Two pointers: start one pointer at the left end (smallest) and one at the right (largest). If their sum is too small, advance the left pointer to increase it. If too large, retreat the right pointer. Each step eliminates an entire row or column of the pair grid.

def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1   # need a bigger number
        else:
            right -= 1  # need a smaller number
    return None

Each iteration the window [left, right] shrinks by at least one. At most n iterations → O(n).

In-place removal / partition

Two pointers also shine when you need to compact an array in-place without allocating extra space. The classic example: remove all occurrences of a value and return the new length.

def remove_val(nums: list[int], val: int) -> int:
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write

read scans every element once; write only advances when it places a keeper. Two passes without an extra array.

Sliding window: fixed-size

A fixed-size window of length k slides across the array. The naive approach recomputes the metric (sum, max, average) from scratch for each of the (n − k + 1) positions → O(n·k).

The trick: the window changes by exactly one element per slide.

• Add the element entering on the right.
• Subtract (or evict) the element leaving on the left.

That is one operation per slide → O(n) total.

Max-sum window of size k

def max_sum_window(nums: list[int], k: int) -> int:
    # Seed the first window
    window_sum = sum(nums[:k])
    best = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i]       # entering element
        window_sum -= nums[i - k]   # leaving element
        best = max(best, window_sum)

    return best

Run it and verify the O(n) sliding against a brute-force O(n·k) recompute:

Sliding window: variable-size

When the window size is not fixed, you need two explicit pointers — a right pointer that expands the window and a left pointer that contracts it when a constraint is violated.

Longest subarray with sum ≤ T

def longest_subarray_sum_leq(nums: list[int], T: int) -> int:
    left = 0
    current_sum = 0
    best = 0

    for right in range(len(nums)):
        current_sum += nums[right]           # expand right

        while current_sum > T:               # violated — contract left
            current_sum -= nums[left]
            left += 1

        best = max(best, right - left + 1)   # valid window

    return best

Why is this still O(n)? Each element is added exactly once (when right reaches it) and removed at most once (when left passes it). The inner while loop may run multiple times on one iteration, but across the entire array left advances at most n times in total. This style of argument — charging the cost of an inner loop to a counter that can only increment n times in total — is called amortized analysis.

Longest substring without repeating characters

The same two-pointer template handles string constraints too:

def longest_unique_substring(s: str) -> int:
    seen: dict[str, int] = {}  # char -> last seen index
    left = 0
    best = 0

    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1   # jump left past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)

    return best

Here the left pointer can jump instead of creeping — still O(n) because right drives the outer loop and each character is processed once.

When does the pattern apply?

The common thread: you can express “does this window satisfy the constraint?” incrementally, meaning you do not need to recheck all k elements when the window shifts by one.

Real-world framing

This is not academic: the pattern shows up everywhere data moves through time or position.

• Rolling/moving averages in time-series dashboards (stock prices, sensor feeds) — exactly the fixed-window sum pattern.
• Network throughput monitoring — bytes transferred in the last 60 seconds without replaying the full log.
• Streaming deduplication — “have I seen this record in the last N events?” with a fixed-size sliding set.
• Query planners — range-scan optimizations in columnar stores use the same incremental-aggregate logic.
• Rate limiting — “how many requests arrived in the last second?” is a sliding count window.

Quick check