Two Pointers & Sliding Window¶

In one sentence

Use two indices that only move forward, so together they take \(O(n)\) steps instead of the \(O(n^2)\) of trying every pair.

1. What problem does it solve?¶

Example — 279B · Books (3-TwoPointers · B, rating 1400)

Valera has \(t\) free minutes and \(n\) books; book \(i\) takes \(a_i\) minutes. He picks a starting book and reads books \(i, i+1, i+2, \dots\) in order, and only starts a book if he can finish it. What is the largest number of books he can read?

In other words: the longest run of consecutive books with total time \(\le t\).

Limits: \(n \le 10^5\), \(a_i \le 10^4\), \(t \le 10^9\).

Input        Output
4 5
3 1 2 1      3

3 3
2 2 3        1

First test: books 1 2 1 take \(4 \le 5\) minutes.

Brute force: try every start \(l\) and extend \(r\) while the sum fits. That is \(O(n^2) = 10^{10}\) in the worst case.

Key observation: all times are positive. So if the window \([l, r]\) fits, every smaller window inside it fits too. When we move \(r\) to the right, the best \(l\) for the new \(r\) is never to the left of the best \(l\) for the old \(r\). Both pointers only move right.

2. The math¶

2.1 Sliding window (same direction)¶

for right = 0 .. n-1:
    1. add a[right] to the window
    2. while the window is invalid: remove a[left], left += 1
    3. the window [left, right] is valid, so update the answer

Why it is \(O(n)\): right moves \(n\) times. left also moves at most \(n\) times in total, because it never moves back. So step 2 runs at most \(n\) times summed over the whole loop, even though it is a while inside a for. That is \(O(n)\) amortized.

Why it is correct: for each right, the loop stops at the smallest left whose window fits (the "fits ⇒ smaller windows fit" property). So \([left, right]\) is the longest fitting window ending at right, and the best over all right is the answer.

Trace on 3 1 2 1 with \(t = 5\) (0-indexed):

right	add	sum after adding	shrink?	window	length	best
0	3	3	no	`3`	1	1
1	1	4	no	`3 1`	2	2
2	2	6	\(6 > 5\): drop `3` → 3	`1 2`	2	2
3	1	4	no	`1 2 1`	3	3

2.2 Opposite ends¶

1669F · Eating Candies (4-Misc · C, rating 1100)

\(n\) candies with weights \(w_i \ge 1\) lie in a row. Alice eats some candies from the left, Bob some from the right, and no candy is eaten twice. They must eat the same total weight. What is the largest total number of candies they can eat?

Input                    Output
4
3
10 20 10                 2
6
2 1 4 2 4 1              6
5
1 2 4 8 16               0
9
7 3 20 5 15 1 11 8 10    7

Put i at the left end and j at the right end, with sums a (Alice) and b (Bob):

a <= b: Alice is behind, so she eats the next candy from the left (i += 1).
a > b: Bob eats the next candy from the right (j -= 1).
Whenever a == b, record \(i + (n - 1 - j)\) candies.
Stop when the pointers cross.

Why nothing is missed. Weights are positive, so Alice's possible totals (\(w_1\), \(w_1 + w_2\), …) form a strictly increasing list, and so do Bob's. We need a value that appears in both lists. Always advancing the smaller one is exactly how you merge two sorted lists, and a merge never skips a common value. Later equal pairs use more candies, so the last one recorded is the best.

Each step moves one pointer inward, so there are at most \(n\) steps.

2.3 When does it apply?¶

pattern	pointers	the property you need
longest / shortest subarray with a condition	same direction (window)	fits ⇒ smaller (or larger) windows fit
count subarrays with sum \(\le K\) (non-negative values)	same direction	adding elements only increases the sum
pair with a target sum on a sorted array	opposite ends	moving one end changes the sum in one direction
equal prefix and suffix sums, merging sorted lists	one pointer per list	both lists sorted

3. Template¶

From our slides (USACO Algorithm — From Bronze to Silver, 16 Jan): the longest subarray with sum \(\le K\). This is Books with K = t.

left = 0
current_sum = 0
max_len = 0
K = 10
nums = [3, 1, 2, 7, 4]

for right in range(len(nums)):
    # 1. Add new element
    current_sum += nums[right]

    # 2. Fix the condition (Shrink window)
    while current_sum > K:
        current_sum -= nums[left]
        left += 1

    # 3. Update Answer
    max_len = max(max_len, right - left + 1)

print(max_len)

For nums = [3, 1, 2, 7, 4] and K = 10 it prints 3 (3 1 2 has sum \(6\), and 7 cannot join without the sum going over \(10\)). The whole algorithm is the three commented steps; only "add", "invalid", and "remove" change between problems.

4. Worked solution — Books¶

The slide template, reading n, t and the list from input.

import sys

input = sys.stdin.readline


def solve():
    n, t = map(int, input().split())
    a = list(map(int, input().split()))

    left = 0
    current_sum = 0
    max_len = 0

    for right in range(n):
        # 1. add a new book
        current_sum += a[right]

        # 2. drop books from the left until the time fits
        while current_sum > t:
            current_sum -= a[left]
            left += 1

        # 3. update the answer
        max_len = max(max_len, right - left + 1)

    print(max_len)


solve()

5. Worked solution — Eating Candies¶

import sys

input = sys.stdin.readline


def solve():
    n = int(input())
    w = list(map(int, input().split()))

    i = 0
    j = n - 1
    a = 0
    b = 0
    best = 0

    while i <= j:
        if a <= b:
            a += w[i]
            i += 1
        else:
            b += w[j]
            j -= 1
        if a == b:
            best = i + (n - 1 - j)

    print(best)


t = int(input())
for _ in range(t):
    solve()

Trace on 2 1 4 2 4 1:

step	eat	`a`	`b`	equal?	`best`
1	Alice `2`	2	0		0
2	Bob `1`	2	1		0
3	Bob `4`	2	5		0
4	Alice `1`	3	5		0
5	Alice `4`	7	5		0
6	Bob `2`	7	7	yes	\(3 + 3 = 6\)

6. Common mistakes¶

Using if instead of while to shrink

One removal may not be enough. Shrink until the window is valid again.

Sliding window with negative numbers

"Sum \(\le K\)" windows need non-negative values. With negatives, adding an element can make the sum smaller, so the monotone property is gone. Use prefix sums instead.

Checking a == b only at the end

In Eating Candies the best moment is usually in the middle. Record the answer every time the sums match.

while i < j in Eating Candies

The last candy (when i == j) may still be eaten by one of them. Use i <= j.

7. Practice¶

Problem	Set	Rating	Idea
279B · Books	3-TwoPointers · B	1400	the slide template (this page)
1669F · Eating Candies	4-Misc · C	1100	opposite ends (this page)
1791C · Prepend and Append	3-TwoPointers · A	800	shrink from both ends
1133C · Balanced Team	3-TwoPointers · C	1200	sort + window with max − min ≤ 5
1354B · Ternary String	3-TwoPointers · D	1200	shortest window containing 1, 2, 3
701C · They Are Everywhere	3-TwoPointers · E, 11-review · B	1500	shortest window with every type
1199C · MP3	7-Intervals · E	1600	sort + window over distinct values

Set 11 (review) also has 702C · Cellular Network, 1777C · Quiz Master, 814C · An impassioned circulation of affection and 1744F · MEX vs MED.

Credits & licenses

Section structure follows USACO Guide — Two Pointers by Darren Yao, Qi Wang, Ryan Chou and David Zhou, licensed CC BY-NC-SA 4.0.
The template in §3 is from our slides. Everything else (amortized argument, merge argument, traces, worked solutions, mistakes) is ours.