Skip to content

Two Pointers & Sliding Window

In one sentence

Keep a window \([l, r]\) over the array; move r forward one step at a time, and move l forward only when the window breaks the rule. Neither pointer ever goes back, so the whole scan is \(O(n)\).

1. What problem does it solve?

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

Valera has \(t\) free minutes and \(n\) books in a row; book \(i\) takes \(a_i\) minutes. He picks any starting book and reads books one after another (never skipping) until he runs out of time; a book he cannot finish does not count. What is the largest number of books he can read?

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

Input        Output
4 5
3 1 2 1      3

3 3
2 2 3        1

In other words: the longest contiguous subarray with sum \(\le t\), the very first problem we templatised.

The naive way. For every start \(l\), extend \(r\) until the sum passes \(t\). That is \(O(n^2)\): \(10^{10}\) steps for \(n = 10^5\).

The observation. Suppose \([l, r]\) is the longest good window ending at \(r\). When \(r\) moves to \(r+1\), the best left end can only stay or move right: a window that starts further left contains \([l-1, r]\), which was already too heavy, and adding a non-negative \(a_{r+1}\) keeps it too heavy. So l never needs to go back.

2. The math

2.1 Why the total work is \(O(n)\)

The for loop moves r exactly \(n\) times. Inside, the while loop moves l, but l only ever increases and never passes \(n\), so all the while iterations together are at most \(n\). Total: at most \(2n\) pointer moves, even though there is a loop inside a loop.

2.2 Trace on sample 1

\(t = 5\), \(a = (3, 1, 2, 1)\).

\(r\) add \(a_r\) sum shrink? \(l\) window length best
0 3 3 no 0 [3] 1 1
1 1 4 no 0 [3 1] 2 2
2 2 6 \(6 > 5\): remove 3 → 3 1 [1 2] 2 2
3 1 4 no 1 [1 2 1] 3 3

2.3 Longest vs shortest

Want Rule while shrinking When to update the answer
longest window that is valid (sum \(\le t\)) shrink while invalid after shrinking, always
shortest window that is valid (sum \(\ge s\)) shrink while still valid without \(a_l\) only if the window is valid

The second row is the extra if check warning from our 10 May recap: after the loop, a "shortest" window may still be too small.

2.4 When it does not work

The argument in §1 needs "a bigger window is never better". With negative numbers a longer window can have a smaller sum, so l might need to move back and the method breaks. Use prefix sums with another idea instead.

3. Lesson notes (15 April and 10 May)

Recap

Binary search and the two-pointers technique are different because they solve different kinds of problems.

Binary search is used when the search space is sorted or when the answer can be checked in a monotonic way. It repeatedly cuts the range in half, so its time complexity is usually O(log n).

Two pointers is used when we process a sequence from one or both ends, often in sorted arrays, strings, or sliding window problems. It moves pointers step by step instead of dividing the search space, so its time complexity is usually O(n).

In short: use binary search to quickly find a value or boundary in an ordered search space, and use two pointers when comparing, scanning, or shrinking/expanding ranges in linear order.

Two Pointers Template

int twoPointers(int n, long long limit, vector<int> a) {
  int l = 0; // 1. init Left pointer
  int ans = 0; // 2. init default answer
  long long sum = 0; // 3. init interval information

  // 4. enumerate each r （moving the Right pointer)
  for (int r = 0; r < n; r++) {
    // 4.x check any special case

    // 5. add a[r] to the interval
    sum += a[r];

    // 6. check if the current is invalid
    while (sum > limit) {
      // 6.a if we reach here
      // means the current interval is invalid
      // we need to at least remove a[l]
      // (but we don't know if it is enough, so we use a while-loop)
      sum -= a[l];
      l++;
    }

    // 6.b if we reach here
    // means the current interval is finally valid

    // 7. compute the current answer and update the final answer
    int len = r - l + 1;
    ans = std::max(ans, len);
  }

  // 8. return the final answer
  return ans;
}

Recap

We found that the scattered pieces of code we usually write can be templatized through functions. Once we have a template, we only need to think about how to integrate the information given in the problem into that template. Once we find the relationship between the given information and the template, we can easily apply the template to solve the problem.

We continued thinking about several key parts of the two-pointer template: add + del + check.

The add function is used to add the element pointed to by the r pointer, usually a[r] or s[r], into our data structure. Here, the data structure refers to something used to maintain information about the current interval. It could be a map, a vector, an int, and so on. For example, it may store the frequency of certain elements in the interval, the number of distinct elements in the interval, or the sum of the interval.

The del function is used to remove the element pointed to by the l pointer from the interval. We need to think about what operation should be performed on the “data structure” when a[l] is removed from the interval: should we delete one frequency count, subtract its value, or, in some cases, decrease the number of distinct elements in the interval?

Finally, the check function is used to check whether we currently can or must remove a[l] from the interval in order to satisfy constraints such as a sum limit, a count limit, or a minimum length requirement. If check passes, it means that we can or need to remove a[l] from the interval to obtain a better result.

Apart from these three functions, do not forget that in scenarios where we are taking the minimum answer, it is possible that check passes but the current interval is too short or still invalid. Therefore, before updating the answer, an additional if check is necessary.

The 10 May code: add, del, check

Longest subarray with sum \(\le 100\):

    // def: longest subarray with sum <= 100
    int sum_of_current_interval = 0;

    auto add = [&](int x) {
        sum_of_current_interval += x;
    };

    auto del = [&](int x) {
        sum_of_current_interval -= x;
    };

    auto check = [&]() {
        return sum_of_current_interval > 100;
    };

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    int ans = 0;
    for (int l = 0, r = 0; r < n; r++) {
        add(a[r]);

        while (check()) {
            del(a[l]);
            l++;
        }
        // when we reach here, we have a valid interval
        int len = r - l + 1;
        ans = max(ans, len);
    }

    cout << ans;

Shortest subarray with sum \(\ge 100\). Note the extra if before updating the answer:

    // def: shortest subarray with sum >= 100
    int sum_of_current_interval = 0;

    auto add = [&](int x) {
        sum_of_current_interval += x;
    };

    auto del = [&](int x) {
        sum_of_current_interval -= x;
    };

    auto check = [&](int x) {
        return sum_of_current_interval - x >= 100;
    };

    int ans = n + 1;
    for (int l = 0, r = 0; r < n; r++) {
        add(a[r]);

        while (check(a[l])) {
            del(a[l]);
            l++;
        }
        // when we reach here, we have a valid interval
        if (sum_of_current_interval >= 100) {
            int len = r - l + 1;
            ans = min(ans, len);
        }
    }

    if (ans == n + 1) {
        cout << "Impossible";
    } else {
        cout << ans << endl;

4. Worked solution — Books

The template with add = "add the minutes", del = "remove them", check = "over the time limit".

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    ll t;
    cin >> n >> t;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    ll sum = 0;
    for (int l = 0, r = 0; r < n; r++) {
        sum += a[r];
        while (sum > t) {
            sum -= a[l];
            l++;
        }
        // [l, r] is the longest valid window ending at r
        ans = max(ans, r - l + 1);
    }

    cout << ans << "\n";
}

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

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. From class, 29 April

We solved these two in class. The window's "information" is different each time, which is the whole point of add / del / check.

1133C · Balanced Team: after sorting, the window is valid while a[r] - a[l] <= 5. The information is just the two endpoints.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    sort(a.begin(), a.end());

    // task: given r
    // find the min l -> [l,r] is balanced
    int ans = 0;
    for (int l = 0, r = 0; r < n; ++r) {
        while (a[r] - 5 > a[l]) {
            l++;
        }
        int len = r - l + 1;
        ans = max(ans, len);
    }

    cout << ans << "\n";
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

1354B · Ternary String: shortest substring containing 1, 2 and 3. The information is a count per digit; we drop a[l] while it appears more than once in the window.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    string s;
    cin >> s;
    int n = s.length();

    vector<int> cnt(4);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = s[i] - '0';
    }

    // * % $

    int ans = n + 1;
    for (int l = 0, r = 0; r < n; r++) {
        cnt[a[r]]++;
        while (cnt[a[l]] > 1) {
            cnt[a[l]]--;
            l++;
        }

        if (cnt[1] && cnt[2] && cnt[3]) {
            int len = r - l + 1;
            ans = min(ans, len);
        }
    }

    if (ans > n) ans = 0;

    cout << ans << "\n";
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

6. Common mistakes

if instead of while when shrinking

Removing one element may not be enough. In the trace above one removal happened to suffice; with a = (5, 5, 1) and \(t = 1\) it does not.

del is not the exact opposite of add

If add increases a counter, del must decrease the same counter. A mismatch silently corrupts the window.

Updating the answer before the window is valid

For "longest", update after the while. For "shortest", check validity first (§2.3).

Negative values

See §2.4: the window idea needs "bigger is never better".

7. Practice

Problem Set Rating Window information
1791C · Prepend and Append 6-TwoPointers · A 800 pointers from both ends (29 April)
279B · Books 6-TwoPointers · B 1400 sum (this page)
1133C · Balanced Team 6-TwoPointers · C 1200 endpoints after sorting
1354B · Ternary String 6-TwoPointers · D 1200 count per digit, shortest
38C · Blinds 6-TwoPointers · E 1400 brute force over the width (29 April)
701C · They Are Everywhere 6-TwoPointers · F 1500 count per letter, number of kinds covered
602B · Approximating a Constant Range 6-TwoPointers · G 1400 counts of values, max − min \(\le 1\)
AIO 2026 · Discount Destinations AIO 2026 Q3 — fixed-length window sum
Credits & licenses
  • §3 joins the two-pointer notes of 15 April (with its binary search vs two pointers recap) and the 10 May recap, unchanged apart from heading levels. The 10 May code and the two 29 April solutions are quoted unchanged from the files written in class.
  • Example, the "l never goes back" argument, trace, comparison table, worked solution and mistakes are ours.