SyntaxPilot
Courses/Competitive Programming/Lesson 10

Competitive Programming · Lesson 10 of 90 · 10 min

Two pointers on contest problems

queued

These are the notes for Competitive Programming episode 10. An original problem, Snack Street, asks for the longest stretch of consecutive shops you can afford. The brute force tries every stretch and gets Time Limit Exceeded on a max test; a shopping-basket idea fixes it: grow the stretch on the right, hand back the oldest snack on the left, never walk back. That is the sliding window, a kind of two pointers, and it runs in O(n). A stress test then shows exactly when it breaks (negative values), we count all windows (and hit an int overflow), and we use pointers from both ends of a sorted array to count pairs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The problem: Snack Street

Problem J · Snack Street (written for this course). n shops stand in a row; a snack at shop i costs a[i] rupees. With a budget of S rupees you walk a stretch of consecutive shops and buy one snack at each. What is the longest stretch you can afford?

1 ≤ n ≤ 2·10^5, 1 ≤ a[i] ≤ 10^9, 1 ≤ S ≤ 10^15.

Sample input Sample output
8 10
2 5 1 3 4 1 1 6
5

The best stretch is 1 3 4 1 1: exactly 10 rupees, 5 shops.

Brute force

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    int best = 0;
    for (int l = 0; l < n; l++) {
        ll sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            if (sum <= S) best = max(best, r - l + 1);
        }
    }
    cout << best << '\n';
    return 0;
}

Correct on the sample (5). A max test made in code (n = 2·10^5, every price 1000, a huge budget) does n²/2 = 2·10^10 additions and got Time Limit Exceeded in the SyntaxPilot compiler:

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

int main() {
    int n = 200000;   // a max test, made in code
    ll S = 1000000000000000LL;
    vector<ll> a(n, 1000);
    auto start = chrono::steady_clock::now();
    int best = 0;
    for (int l = 0; l < n; l++) {
        ll sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            if (sum <= S) best = max(best, r - l + 1);
        }
    }
    auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
    cout << "best " << best << ", time " << ms << " ms\n";
    return 0;
}

The waste: every new l throws away the sum just built and starts over.

The idea: walking the street with a basket

Walking with a basket In code
Buy at the next shop sum += a[r], then r moves right: grow the window
Over budget? Return the oldest snack sum -= a[l], l++: shrink the window
You never walk back l and r only move forward
Note your biggest basket best = max(best, r - l + 1)

A window is the stretch a[l..r]; the sliding window moves both ends forward. Two pointers is the general name for algorithms with two indices that only move in one direction.

Trace on the sample (S = 10):

step window sum action
r = 2 2 5 1 8 length 3
r = 3 2 5 1 3 11 > 10 drop 2 → 5 1 3, sum 9
r = 4 5 1 3 4 13 > 10 drop 5 → 1 3 4, sum 8
r = 6 1 3 4 1 1 10 length 5 (best)
r = 7 1 3 4 1 1 6 16 > 10 drop 1, 3, 4 → 1 1 6, sum 8

The sliding window

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    int best = 0, l = 0;
    ll sum = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > S) sum -= a[l++];
        best = max(best, r - l + 1);
    }
    cout << best << '\n';
    return 0;
}

Output on the sample: 5. On the same max test as the brute force:

best 200000, time 0 ms

Why O(n) with a while inside a for? r moves n times. l only moves forward and never past r + 1, so across the whole run it moves at most n times. Total work ≤ 2n. Counting the total moves of a loop over the whole run, instead of its worst case each time, is called amortised analysis.

Stress test: where it breaks (real output)

Twist: some shops give coupons, so a price can be negative. A stress test (episode 5) compares the window with the brute force on 1000 random small arrays (prices from −3 to 5):

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

int fast(vector<ll> &a, ll S) {
    int n = a.size(), best = 0, l = 0;
    ll sum = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (l <= r && sum > S) sum -= a[l++];
        best = max(best, r - l + 1);
    }
    return best;
}

int brute(vector<ll> &a, ll S) {
    int n = a.size(), best = 0;
    for (int l = 0; l < n; l++) {
        ll sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            if (sum <= S) best = max(best, r - l + 1);
        }
    }
    return best;
}

int main() {
    mt19937 rng(7);
    for (int it = 1; it <= 1000; it++) {
        int n = rng() % 6 + 1;
        ll S = rng() % 10;
        vector<ll> a(n);
        for (auto &x : a) x = (int)(rng() % 9) - 3;
        if (fast(a, S) != brute(a, S)) {
            cout << "Mismatch on test " << it << ": S = " << S << ", a =";
            for (ll x : a) cout << ' ' << x;
            cout << "\nbrute = " << brute(a, S) << ", fast = " << fast(a, S) << '\n';
            return 0;
        }
    }
    cout << "All 1000 tests passed\n";
    return 0;
}

Output:

Mismatch on test 2: S = 9, a = 1 5 4 -2 5 3
brute = 4, fast = 3

1 5 4 -2 costs 8: four shops. The window reached 1 5 4 (sum 10 > 9), dropped the 1 for good, and never saw that the −2 would bring the sum back down. With prices from 1 to 9 instead (x = rng() % 9 + 1;) the same stress test prints All 1000 tests passed.

The rule (monotonicity). With a[i] ≥ 1, a longer window never costs less. If [l, r] is too expensive, so is [l, r + 1], so l can never start a better answer and dropping it is safe. Two pointers need this one-directional property. With negative values it's gone; use other tools (for example prefix sums with sorting).

Counting all affordable windows (and the int overflow)

Problem J2. Count all stretches with sum ≤ S. When the inner while stops, every start from l to r works with this r: that's r − l + 1 windows.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    int l = 0;
    ll sum = 0, ways = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > S) sum -= a[l++];
        ways += r - l + 1;
    }
    cout << ways << '\n';
    return 0;
}

Sample output: 24 (a brute force over all stretches agrees).

Max test with int ways (n = 2·10^5, every price 1, a huge budget):

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

int main() {
    int n = 200000;   // a max test, made in code
    ll S = 1000000000000000LL;
    vector<ll> a(n, 1);
    int l = 0;
    ll sum = 0;
    int ways = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > S) sum -= a[l++];
        ways += r - l + 1;
    }
    cout << ways << '\n';
    return 0;
}

Output:

-1474736480

Every stretch is affordable, so the answer is n(n+1)/2 = 20,000,100,000, far past int's limit of about 2.1·10^9. With ll ways the output is 20000100000.

Pointers from both ends

Problem J3. Count pairs i < j with a[i] + a[j] ≤ K. Sort, put i on the smallest and j on the largest:

  • If a[i] + a[j] ≤ K, then a[i] also fits with every element between them (they're ≤ a[j]): pairs += j − i, then i++.
  • Otherwise a[j] is too big even with the smallest left: j--.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll K;
    cin >> n >> K;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    int i = 0, j = n - 1;
    ll pairs = 0;
    while (i < j) {
        if (a[i] + a[j] <= K) {
            pairs += j - i;
            i++;
        } else {
            j--;
        }
    }
    cout << pairs << '\n';
    return 0;
}

Input 6 10 / 7 1 4 9 3 6 (sorted: 1 3 4 6 7 9), output: 9 (1 pairs with 3, 4, 6, 7, 9; 3 with 4, 6, 7; 4 with 6).

Solutions in C++, Java and Python (Snack Street)

C++: the sliding-window program above.

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer t = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(t.nextToken());
        long S = Long.parseLong(t.nextToken());
        long[] a = new long[n];
        t = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(t.nextToken());
        int best = 0, l = 0;
        long sum = 0;
        for (int r = 0; r < n; r++) {
            sum += a[r];
            while (sum > S) sum -= a[l++];
            best = Math.max(best, r - l + 1);
        }
        System.out.println(best);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, S = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n]))
    best = l = s = 0
    for r in range(n):
        s += a[r]
        while s > S:
            s -= a[l]
            l += 1
        best = max(best, r - l + 1)
    print(best)

main()

All three print 5 on the sample.

Brute force vs optimal

All (l, r) Sliding window Sort + both ends
Time O(n²) O(n) O(n log n)
At n = 2·10^5 2·10^10 (TLE) ≤ 4·10^5 moves ≈ 3.6·10^6
Needs nothing monotonic window (a[i] ≥ 0) sorted array

Common mistakes (and the real messages)

Mistake What you see Why Fix
Window with negative values brute = 4, fast = 3 dropping l is no longer safe only when growing is monotonic
int ways -1474736480 about n²/2 windows long long ways
Resetting r = l for every l Time Limit Exceeded that's the O(n²) brute force again pointers never move back
Both-ends walk on an unsorted array wrong count the j-- argument needs order sort first
int sum wrong answers on big prices sums reach 2·10^14 long long sum

Mini project: shortest stretch with sum ≥ S

Same window, the other way round: grow r; while the sum is at least S, record r − l + 1 and shrink from the left.

int best = INT_MAX, l = 0;
ll sum = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];
    while (sum >= S) {
        best = min(best, r - l + 1);
        sum -= a[l++];
    }
}

On the sample with S = 10 the answer is 4 (for example 2 5 1 3 = 11). Print −1 if best stays INT_MAX.

Practice

  1. Longest stretch with at most 2 different prices on the sample.

    Answer Keep a count of each price in the window (a <code>map</code>); while it has more than 2 keys, shrink. The answer is <code>3</code> (<code>4 1 1</code> or <code>1 1 6</code>).

  2. Count pairs with a[i] + a[j] exactly 10 in 7 1 4 9 3 6.

    Answer <code>3</code>: (1, 9), (4, 6), (7, 3). Sort and walk from both ends; when the sum is 10 count it and move both (handle equal values carefully).

  3. Why is the sliding window O(n) even though it has a nested loop?

    Answer <code>l</code> moves at most n times in total across the whole run, so the inner loop's total work is n.

  4. Does the window work if prices can be 0?

    Answer Yes: a longer window still never costs less (sums are non-decreasing as the window grows), so dropping <code>l</code> is still safe.

Quick quiz

S = 7, prices 4 1 2 1 5 1. Longest affordable stretch?

A) 2 · B) 3 · C) 4 · D) 5

Answer

B. 4 1 2 = 7 and 1 2 1 = 4 have length 3. Every stretch of 4 costs at least 8.

Interview questions

  1. Longest subarray with sum ≤ S, all elements positive? Sliding window, O(n).
  2. Why does the sliding window fail with negative numbers? Growing the window can make the sum smaller, so a dropped left end might have started a better answer.
  3. Number of subarrays with sum ≤ S? Sliding window and add r − l + 1 for each r; use 64-bit counts.
  4. Count pairs with sum ≤ K? Sort, two pointers from both ends: O(n log n).
  5. What is amortised analysis? Bounding the total cost of all operations over the run instead of the worst case of each one.

Glossary

Term Meaning Example
Subarray / stretch Consecutive elements a[l..r] 1 3 4 1 1
Window The current stretch between the two pointers l = 2, r = 6
Two pointers Two indices that only move in one direction l and r
Sliding window Two pointers that grow on the right and shrink on the left the basket
Amortised analysis Counting total work over the whole run l moves ≤ n times
Monotonicity Growing only changes the value one way sums never shrink when all a[i] ≥ 0
Stress test Random small tests comparing a fast solution with a brute force Mismatch on test 2
Max test An input at the largest allowed size n = 2·10^5 made in code
Overflow A value exceeds its type's range and wraps around -1474736480
mt19937 C++'s Mersenne Twister random generator mt19937 rng(7)

Summary

  • Trying every stretch is O(n²): 2·10^10 at n = 2·10^5, TLE.
  • Sliding window: grow right, shrink left, never move back. O(n) by amortised analysis.
  • It needs monotonicity: with negative values the stress test found brute = 4, fast = 3.
  • Count windows with ways += r − l + 1 in a long long (int printed -1474736480).
  • Sorted array + pointers from both ends counts pairs in one walk.

Next episode: binary search on the answer: guess it, check it, halve the range.