Two Pointers & Sliding Window

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

Two pointers and the sliding window escape that by keeping one or two indices that only ever move forward. Because each element is passed at most twice — once by each pointer — the total work is O(n), no matter how busy the loop looks from the inside. Think of reading a book with two bookmarks rather than re-reading every earlier page each time you turn one.

Two pointers: closing in from both ends

Suppose a sorted array and a target, and you want two values that sum to it. Brute force tries every pair — O(n²). Instead, put one pointer at the smallest value and one at the largest. If their sum is too small, the only way to grow it is to move the left pointer right; if too large, move the right pointer left. Each step rules out a whole row of pairs at once:

def two_sum_sorted(nums, target):
    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 sum
        else:
            right -= 1       # need a smaller sum
    return None

print(two_sum_sorted([2, 7, 11, 15], 18))

(1, 3)

The window [left, right] shrinks by at least one each step, so the loop runs at most n times — O(n) instead of O(n²), and with no extra memory.

The sliding window: don’t recompute, adjust

Now slide a window of fixed length k across an array, asking for the largest window sum. The naive way recomputes each window’s sum from scratch — O(n·k). But neighbouring windows differ by just two elements: the one entering on the right and the one leaving on the left. So keep a running sum, and on each slide add the newcomer and subtract the leaver.

def max_sum_window(nums, k):
    window = sum(nums[:k])              # seed the first window
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]  # add entering, subtract leaving
        best = max(best, window)
    return best

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 2]
print("sliding window:", max_sum_window(nums, 4))
print("brute force   :", max(sum(nums[i:i+4]) for i in range(len(nums) - 3)))

sliding window: 22
brute force   : 22

Same answer, but the sliding version does one add-and-subtract per slide — O(n) — where the brute force re-adds k elements every time, O(n·k).

The variable-size window

When the window’s size is not fixed, you grow it with a right pointer and shrink it with a left pointer whenever a constraint breaks. Take “the longest run whose sum stays within a limit T”:

def longest_within(nums, T):
    left = total = best = 0
    for right in range(len(nums)):
        total += nums[right]            # expand to the right
        while total > T:                # over the limit — shrink from the left
            total -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_within([2, 1, 5, 1, 3, 2], 8))

4

The inner while sometimes runs several times in one step, so why is this still O(n)? Because left only ever moves forward, and it can advance at most n times across the entire run. Charging the inner loop’s cost to that one-way counter — rather than counting it per outer step — is exactly amortised analysis, the same reasoning behind a list’s O(1) append.

The common thread: you can update “does this window satisfy the constraint?” incrementally, without rechecking all k elements each shift. That is why rolling averages, network-throughput-in-the-last-60-seconds, streaming dedup, and rate limiters all wear this same shape.

Practice