The Two Pointers Technique: Sliding Windows in O(n)

Many array problems ask about contiguous segments: the longest one with some property, the number of segments below a limit, and so on. Checking every segment takes O(n²) time. The two pointers technique often brings that down to O(n) by moving a window across the array instead of rebuilding it from scratch.

The problem

Valera has t free minutes and a row of n books. Book i takes a_i minutes to read. He picks a starting book and reads books in order until he runs out of time (he never stops halfway through a book). What is the largest number of books he can read? This is Codeforces 279B – Books, with n up to 10⁵.

In other words: find the longest contiguous segment whose sum is at most t.

Brute force first

Try every start l, extend r while the sum stays within t, and remember the best length. That is correct but O(n²) in the worst case, about 10¹⁰ steps here.

The key observation

Suppose the best window that ends at position r starts at position l. When we move to r + 1, the best window ending there cannot start before l: if it did, it would contain the window [l − 1, r], whose sum is already too large (all times are positive). So the left end only ever moves right.

That gives the algorithm:

1. Move the right pointer one step and add the new book to the running sum.
2. While the sum is more than t, remove the leftmost book and move the left pointer right.
3. The window [left, right] is now the longest valid one ending at right. Update the answer.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long t;
    cin >> n >> t;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    int best = 0;
    long long sum = 0;   // sum of a[left..right]
    int left = 0;
    for (int right = 0; right < n; right++) {
        sum += a[right];
        while (sum > t) {        // window too expensive: shrink from the left
            sum -= a[left];
            left++;
        }
        best = max(best, right - left + 1);
    }
    cout << best << '\n';
    return 0;
}

Walking through an example

t = 5, books 3 1 2 1.

• right = 0: window [3], sum 3. Best = 1.
• right = 1: window [3, 1], sum 4. Best = 2.
• right = 2: sum 6 > 5, so drop the 3. Window [1, 2], sum 3. Best stays 2.
• right = 3: window [1, 2, 1], sum 4. Best = 3.

Why it is O(n)

There is a while loop inside a for loop, which looks quadratic. But each pointer only moves forward, and each moves at most n times in total. Counting all the steps of both pointers gives at most 2n, so the whole algorithm is O(n) time and O(1) extra memory.

When two pointers works, and when it does not

The technique relies on the window property being monotonic: shrinking a valid window keeps it valid, and growing an invalid one keeps it invalid. With positive numbers and “sum ≤ t”, that holds.

It breaks if the array can contain negative numbers. Then adding an element can make the sum smaller, and the left pointer might need to move back. Those problems usually need prefix sums with sorting or a data structure instead.

Another common form: two pointers on a sorted array

To find two numbers in a sorted array that add up to x, start one pointer at each end. If their sum is too small, move the left pointer right; if too large, move the right pointer left. Each step rules out one element for good, so it is also O(n) after sorting. CSES 1640 – Sum of Two Values is a good exercise for this version.

Practice problems

• Codeforces 279B – Books: the problem in this post.
• Codeforces 676C – Vasya and String: longest window with at most k characters changed.
• CSES 1640 – Sum of Two Values: the sorted-array version.

Two pointers pairs naturally with run-counting problems like 266A, where you also compare each element with what came before.

Prefix Sums Explained: Answer Range Sum Queries in O(1)

Prefix sums are one of the first techniques that make a beginner's solutions dramatically faster. The idea takes a minute to learn, and it turns up everywhere: range sums, counting problems, 2D grids, and as a building block inside harder algorithms.

The problem

You have an array of n numbers and q questions. Each question gives two positions l and r and asks for a_l + a_l+1 + … + a_r. Both n and q can be 2 × 10⁵.

Looping from l to r for each question costs up to n steps per question, so 4 × 10¹⁰ steps in the worst case. That is far too slow. We want each answer in constant time.

The idea

Build a second array where each entry stores the total of everything up to that point:

pre[0] = 0
pre[i] = a[1] + a[2] + ... + a[i] = pre[i - 1] + a[i]

Building it takes one pass. Now notice that the sum from l to r is “everything up to r” minus “everything before l”:

sum(l, r) = pre[r] − pre[l − 1]

That is one subtraction per question, no matter how wide the range is.

Worked example

Take the array 3 1 4 1 5 9 (positions 1 to 6).

i	0	1	2	3	4	5	6
a[i]	–	3	1	4	1	5	9
pre[i]	0	3	4	8	9	14	23

The sum from position 3 to 5 is pre[5] − pre[2] = 14 − 4 = 10, and indeed 4 + 1 + 5 = 10. The sum of the whole array is pre[6] − pre[0] = 23.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    // pre[i] = a[1] + a[2] + ... + a[i], with pre[0] = 0
    vector<long long> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }
    return 0;
}

The input format matches CSES 1646 – Static Range Sum Queries: n and q, then the array, then q lines with l and r.

Complexity

O(n) to build the prefix array and O(1) per query, so O(n + q) in total, with O(n) extra memory.

Why the extra zero matters

Starting the array with pre[0] = 0 and using 1-based positions means the formula works even when l = 1, because pre[l − 1] = pre[0] = 0. If you use 0-based indexing without that extra slot, you need a special case for queries starting at the first element, and special cases are where bugs live.

Common mistakes

• Overflow. 2 × 10⁵ values of up to 10⁹ add up to 2 × 10¹⁴. Store prefix sums in long long even if the input fits in int.
• Off by one. It is pre[r] − pre[l − 1], not pre[r] − pre[l]. The second version drops a_l.
• Slow input. With 2 × 10⁵ queries, unbuffered cin can be the bottleneck. The two lines at the top of main fix that.

Beyond sums

The same trick works for anything you can “undo”. Prefix XOR answers range XOR queries, because x XOR x = 0. Prefix counts answer questions like “how many even numbers are between l and r”: build an array that adds 1 for each position that satisfies the condition. In 2D, the sum of a rectangle can be found from four prefix values using inclusion–exclusion.

It does not work for minimum or maximum, because you cannot subtract a minimum. Those need other structures, such as a sparse table or a segment tree.

Practice problems

• CSES 1646 – Static Range Sum Queries: the exact problem above.
• Codeforces 313B – Ilya and Queries: a prefix count of positions where two neighbouring characters are equal.
• Codeforces 433B – Kuriyama Mirai's Stones: two prefix arrays, one on the original order and one after sorting.

If you have not yet read it, my post on how to read constraints starts from the same “range sum” example and explains why 2 × 10⁵ queries rule out the simple loop.