AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 4

Part 1 · Foundations · Chapter 4

Two Pointers, Sliding Windows and Prefix Sums

Three techniques that turn a nested loop into a single pass. Learn them here and you will spot them in half the problems you meet for the rest of the course.

Reading

—

Focus

O(n²) → O(n)

Techniques

Applies to

Arrays · strings

By the end of this chapter you can

Recognise when a nested loop over an array can be collapsed into a single pass
Apply converging two pointers, and state the property that makes the discarded half safe to discard
Maintain a sliding window with an incrementally updated summary rather than a recomputed one
Build a prefix-sum table and answer any range query in O(1)
Name the invariant a two-pointer loop maintains, and use it to debug the loop when it is wrong

1The shape these techniques attack

All three of this chapter's techniques answer the same complaint about the same kind of code.

Here is the pattern. Some question about an array is answered by trying every pair, or every starting position, or every range:

the_shape.py

# A
for i in range(n):
    for j in range(i + 1, n):        # every pair          → O(n²)
        if xs[i] + xs[j] == target:
            return True

# B
for i in range(n - 2):
    total = xs[i] + xs[i+1] + xs[i+2]   # recomputed from scratch → O(n·k)

# C ... asked a million times
for i in range(4, 10):               # a fresh loop per question   → O(n) each
    total += xs[i]

In each case the inner work overlaps almost entirely with the work just done. The window starting at index 4 shares two of its three values with the window starting at index 3. The sum from 4 to 9 shares eight of its terms with the sum from 4 to 10. We keep re-deriving what we already knew.

The one idea behind all three techniques

Carry information forward instead of recomputing it. If step k and step k+1 mostly overlap, find the small update that takes you from one to the other, and the nested loop collapses.

Three variations on that idea, in increasing order of subtlety:

Technique	Use it when	What is carried forward
Two pointers, converging	The array is sorted and you are looking for a pair	The knowledge that everything outside the pointers is ruled out
Two pointers, same direction (sliding window)	You want the best contiguous run	A running summary of the current window
Prefix sums	You will be asked about many different ranges	A table of cumulative totals, computed once

2Converging pointers

Two indices start at opposite ends and walk toward each other. Each step permanently eliminates a whole region.

The dictionary

Looking for a word in a paper dictionary, you never start at page 1. You open somewhere, see you are too far in, and throw away everything after that page without reading it.

You are allowed to do that because the dictionary is sorted. Sortedness is not a convenience here — it is the licence to discard.

The classic use: given a sorted array, find two values summing to a target. Brute force is every pair, O(n²). Watch the pointer version:

The logic at each step is short and worth saying precisely:

If xs[lo] + xs[hi] is too small, no pair using xs[lo] can work — xs[hi] is already the largest partner available. So lo can move right, and every pair involving the old lo is eliminated at once.
If the sum is too large, the mirror argument eliminates every pair involving xs[hi].

Each step throws away an entire row or column of the pair matrix. There are 2n such rows and columns, so the loop terminates in at most n steps.

two_pointers.py

def two_sum_sorted(xs, target):
    """xs must be sorted ascending. Returns (i, j) or None."""
    lo, hi = 0, len(xs) - 1
    while lo < hi:
        s = xs[lo] + xs[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1        # need a bigger sum, and hi is already maximal
        else:
            hi -= 1        # need a smaller sum, and lo is already minimal
    return None

# O(n) time, O(1) space.
# The brute force is O(n²) — and on 10,000 items that is 50 million
# comparisons versus 10,000.

The precondition is the whole algorithm

On an unsorted array this is simply wrong — the elimination argument evaporates, because a smaller value later in the array could still form the pair.

If the input is not sorted, you have a choice: sort first (O(n log n), then O(n)) or use a hash set (O(n) total, at the cost of O(n) space). Both are in the exercises.

3The sliding window

Both pointers move the same way. The window between them holds a summary that is updated, never rebuilt.

The train window

Watching the countryside from a train, you do not re-observe the entire visible landscape every second. One field leaves the left edge of the window, one field enters the right, and your picture updates by two small edits.

The question: what is the largest sum of any k consecutive values? The naive answer adds up k numbers at every position, O(n·k). The window version adds one and subtracts one:

fixed_window.py

def max_window_sum(xs, k):
    if len(xs) < k:
        return None
    total = sum(xs[:k])          # build the first window ONCE — O(k)
    best = total
    for end in range(k, len(xs)):
        total += xs[end] - xs[end - k]   # ← the entire trick, in one line
        best = max(best, total)
    return best

# O(n) regardless of k. The naive version is O(n·k).

Variable-size windows

The more powerful version lets the window grow and shrink to maintain a condition. The pattern is always the same three lines:

variable_window.py

left = 0
for right in range(len(xs)):
    add xs[right] to the window                 # 1. always expand right

    while the window violates the condition:    # 2. shrink from the left
        remove xs[left] from the window            until it is legal again
        left += 1

    record the answer for this window           # 3. every window here is valid


# Why this is O(n) despite the inner while loop:
# `right` advances n times total, and `left` advances at most n times total.
# Each index moves forward only, and never resets. 2n moves, so O(n).

That last comment matters. A while inside a for looks quadratic and is not, because the inner loop's counter never goes backwards. This is the same amortised argument as the dynamic array, and you will meet it again with the monotonic stack in Chapter 6.

How to recognise a window problem

Look for the words contiguous, consecutive, substring, or subarray, together with longest, shortest, or maximum.

If the elements do not have to be adjacent, it is not a window problem — it is probably dynamic programming, Chapter 25.

4Prefix sums: pay once, answer forever

When the same array will be interrogated many times about many different ranges, precompute.

Suppose you will be asked, thousands of times, for the sum of some range xs[i:j]. Answering each question with a loop is O(n) per question. Instead, spend one O(n) pass up front:

prefix_sums.py

def build_prefix(xs):
    """prefix[i] = sum of xs[0:i].  Note: one longer than xs."""
    prefix = [0] * (len(xs) + 1)
    for i, x in enumerate(xs):
        prefix[i + 1] = prefix[i] + x
    return prefix

def range_sum(prefix, lo, hi):
    """Sum of xs[lo:hi+1], inclusive of both ends. O(1)."""
    return prefix[hi + 1] - prefix[lo]

xs = [3, 7, 2, 8, 5, 1, 9, 4]
p = build_prefix(xs)          # [0, 3, 10, 12, 20, 25, 26, 35, 39]
range_sum(p, 2, 5)            # 2 + 8 + 5 + 1 = 16
                              # = p[6] - p[2] = 26 - 10 = 16

Why the table is one longer

prefix[0] = 0 represents the sum of the empty prefix. Without it, the range formula needs a special case for lo == 0, and that special case is where the off-by-one bugs live.

This is a recurring design idea: add a sentinel so the general formula covers the edge case. You will see it again in dynamic programming tables in Chapter 25.

The generalisation

Prefix sums are one instance of a broader move: precompute a cumulative summary so that any range becomes a difference. The same trick works for anything with an inverse operation.

Operation	Prefix array holds	Range query
Sum	Running total	`p[hi+1] - p[lo]`
XOR	Running XOR	`p[hi+1] ^ p[lo]`
Count of a property	Running count	`p[hi+1] - p[lo]`
Product (no zeros)	Running product	`p[hi+1] / p[lo]`
Minimum	— does not work	No inverse; use a sparse table or a segment tree

The last row is the important one. Minimum has no inverse operation — knowing the min of the first ten and the min of the first four tells you nothing about the min of items 5–10. That gap is exactly what segment trees exist to fill, in Chapter 29.

Prefix sums only pay off if you ask more than once

Building the table costs O(n). If you have exactly one range query, just loop — you will do the same work with less code. The technique wins when the number of queries is large, or when the array is queried inside a loop.

5Putting them together

Most real problems want a combination. Here is one, solved three ways, each better than the last.

The problem. Given an array of positive integers and a target, find the length of the shortest contiguous subarray whose sum is at least the target. Return 0 if none exists.

Attempt 1 — every subarray

attempt1.py

def shortest_v1(xs, target):          # O(n³) — and it is honest about it
    best = float("inf")
    for i in range(len(xs)):
        for j in range(i, len(xs)):
            if sum(xs[i:j+1]) >= target:  # ← this sum() is the third loop
                best = min(best, j - i + 1)
    return 0 if best == float("inf") else best

Attempt 2 — prefix sums remove the inner sum

attempt2.py

def shortest_v2(xs, target):          # O(n²)
    p = [0]
    for x in xs:
        p.append(p[-1] + x)
    best = float("inf")
    for i in range(len(xs)):
        for j in range(i, len(xs)):
            if p[j+1] - p[i] >= target:   # now O(1) instead of O(n)
                best = min(best, j - i + 1)
                break                     # shortest for this i; stop
    return 0 if best == float("inf") else best

Attempt 3 — a variable window removes the outer loop too

attempt3.py

def shortest_v3(xs, target):          # O(n)
    left = 0
    total = 0
    best = float("inf")
    for right, x in enumerate(xs):
        total += x                        # 1. expand right
        while total >= target:            # 2. shrink while still valid
            best = min(best, right - left + 1)
            total -= xs[left]
            left += 1
    return 0 if best == float("inf") else best

# Why it is correct: for each `right`, the while loop pulls `left` as far
# right as it can go while the window still meets the target. So we test
# exactly the shortest valid window ending at each position — and the answer
# must be one of those.
#
# Why it is O(n): left and right each advance at most n times, total.

Attempt 1

O(n³)

Attempt 2

O(n²)

Attempt 3

O(n)

Space (v3)

O(1)

On an array of 10,000 items that is roughly a trillion operations, then a hundred million, then ten thousand. The code got shorter at each step, which is common: the fast version usually expresses the structure of the problem more directly than the slow one.

The precondition, again

Attempt 3 relies on all values being positive. With negative numbers, adding an element can decrease the total, so shrinking the window is no longer guaranteed to reduce the sum, and the whole argument collapses. That problem needs prefix sums plus a monotonic structure. Whenever a window solution looks too easy, check whether it silently assumed monotonicity.

What to carry forward

All three techniques share one idea: carry information forward instead of recomputing it when consecutive steps overlap.
Converging pointers need sorted input. Each step eliminates an entire row or column of the pair space — that is why the loop is O(n).
Sliding windows update a summary incrementally. A while-loop inside a for-loop is still O(n) when both indices only move forward.
Prefix sums turn any range query into one subtraction, but only after an O(n) build — worth it only if you ask more than once.
Prefix tricks need an inverse operation. Sum and XOR work; minimum does not, which is why segment trees exist.
Every one of these has a precondition — sorted, or positive. When a fast solution looks too easy, find the assumption it is leaning on.

>_Playground

The same problem, three ways. Change N and watch the gap widen exactly as predicted.

scratch.pypython not loaded

import time, random

random.seed(7)
N = 2000
xs = [random.randint(1, 20) for _ in range(N)]
target = 300

def v1(xs, target):                 # O(n^2), with prefix sums
    p = [0]
    for x in xs:
        p.append(p[-1] + x)
    best = float("inf")
    for i in range(len(xs)):
        for j in range(i, len(xs)):
            if p[j+1] - p[i] >= target:
                best = min(best, j - i + 1)
                break
    return 0 if best == float("inf") else best

def v2(xs, target):                 # O(n), sliding window
    left = total = 0
    best = float("inf")
    for right, x in enumerate(xs):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= xs[left]
            left += 1
    return 0 if best == float("inf") else best

t0 = time.perf_counter(); a = v1(xs, target); t1 = time.perf_counter()
b = v2(xs, target);                            t2 = time.perf_counter()

print(f"same answer? {a == b}   (both said {a})")
print(f"O(n^2): {(t1-t0)*1000:8.2f} ms")
print(f"O(n)  : {(t2-t1)*1000:8.2f} ms")
print(f"speedup: {(t1-t0)/max(t2-t1,1e-9):,.0f}x")

# Now set N = 4000. The O(n^2) time should roughly quadruple
# while the O(n) time roughly doubles.

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 5 — Linked Lists

A treasure hunt where each clue tells you where the next clue is. Splice into the middle for free — but never skip ahead.

Continue →