Two pointers

The two pointers technique finds the longest run of consecutive elements of an array whose sum stays within a limit, or a pair with a given sum in a sorted array, by moving two indices that each go in one direction only. It replaces a double loop of n^2 steps with one pass of at most $2n$. The run search needs elements that are not negative; with negative numbers it can skip the answer.

Explanation

A playlist has 5 songs of 3, 4, 2, 5 and 1 minutes. Your bus ride takes 8 minutes. You can start at any song, the songs play in order, and you don't want a song cut off when you get off. How many songs in a row can you hear to the end?

Fig. 1. The longest run of songs that fits into 8 minutes is blue.

Songs 3 to 5, blue in Fig. 1, take 2 + 5 + 1 = 8 minutes: 3 songs. Songs 1 and 2 take 7 minutes, and song 3 would make it 9.

A longer playlist is harder to check by eye. Take 8 songs of 4, 2, 2, 3, 2, 2, 6 and 2 minutes, and a ride of 12 minutes. What is the longest run of songs that fits?

The obvious way is to go through the playlist once. Play from song 1 while the songs fit. When the next song doesn't fit, start a new run from that song. Songs 1 to 4 take 4 + 2 + 2 + 3 = 11 minutes, and song 5 would make 13. So start again at song 5: songs 5 to 8 take 2 + 2 + 6 + 2 = 12 minutes. Both runs have 4 songs, the brackets in Fig. 2.

Fig. 2. Starting over at the outlined song 5 gives two runs of 4 songs (the brackets). The blue run of 5 songs starts inside the first one.

But songs 2 to 6 take 2 + 2 + 3 + 2 + 2 = 11 minutes: 5 songs, the blue run. Starting over threw away songs 2, 3 and 4 together with song 1, and the best run begins inside the old one.

The safe way is to try every first song: start there and add songs until the next one doesn't fit. This finds the 5 songs that start at song 2, but it repeats work. Songs 3 to 6 are added again for the first song 2, again for 3, and again for 4. On 8 songs it takes 30 additions, counting the 4 songs that were tried and didn't fit (grey in Fig. 3). If every song fits, first song 1 adds 10^5 songs, first song 2 adds 10^5 - 1, and so on: about 10^5 \cdot 10^5 / 2 = 5 \cdot 10^9 additions for 10^5 songs. That is far too many, since a common rule of thumb puts only about 10^8 simple operations in a second.

Fig. 3. One row per first song. The last song of the run never moves left.

In Fig. 3 the rows end at songs 4, 6, 6, 6, 8, 8, 8 and 8. When the first song moves one place to the right, the old run loses its first song. Every length is positive, so its total gets smaller and it still fits. There is no need to add those songs again.

So keep the run and only change its first and last song. Add the next song at the end. While the run is too long, drop its first song. Then record the run's length if it is the longest so far. Each song is added once and dropped at most once: on this playlist that is 8 additions and 4 drops instead of 30 additions.

This is the two pointers technique, also called a sliding window when the two pointers mark a run. A pointer here is an index into the array, not a C++ pointer. The first and the last song of the run are two indices, and each of them only moves forward.

Fig. 4 runs the whole scan on the 8-song playlist.

Song 1 (4 min) is added: the run takes 4 minutes, within 12. The longest run so far has 1 song.

Song 2 (2 min) is added: the run takes 6 minutes, within 12. The longest run so far has 2 songs.

Song 3 (2 min) is added: the run takes 8 minutes, within 12. The longest run so far has 3 songs.

Song 4 (3 min) is added: the run takes 11 minutes, within 12. The longest run so far has 4 songs.

Song 5 (2 min) is added: the run takes 13 minutes, over 12.

Song 1 is dropped: the run takes 9 minutes, within 12 again.

Song 6 (2 min) is added: the run takes 11 minutes, within 12. The longest run so far has 5 songs.

Song 7 (6 min) is added: the run takes 17 minutes, over 12.

Song 2 is dropped: the run takes 15 minutes, still over 12.

Song 3 is dropped: the run takes 13 minutes, still over 12.

Song 4 is dropped: the run takes 10 minutes, within 12 again.

Song 8 (2 min) is added: the run takes 12 minutes, within 12. The scan is over: the longest run has 5 songs, songs 2 to 6.

1/12

Fig. 4. The two pointers scan with a 12-minute ride. The light blue songs are the current run, from l to r; the song just added is dark blue, or red when the run is over 12 minutes; grey songs are dropped for good.

After each song is added and the drops are done, the shaded songs are the longest run that ends at that song. For songs 1 to 8 these runs have 1, 2, 3, 4, 4, 5, 3 and 4 songs, and the answer 5 is the largest of them.

Two items for a gift card

The same idea finds a pair. You have a gift card for 13 euros and want to buy two different items that cost exactly 13 together. The shop lists its prices in increasing order: 1, 3, 4, 6, 9 and 11 euros.

The obvious way is to try every pair: 1 + 3, 1 + 4, and so on up to 9 + 11. That is 15 sums for 6 prices, and about n^2/2 for $n$ prices, so 5 \cdot 10^9 for 10^5 prices. Because the prices are in order, one check can rule out a whole price.

Start with the cheapest and the most expensive price: 1 + 11 = 12, too little. Even the most expensive price doesn't bring 1 up to 13, so 1 is in no pair: move on to the next cheapest. Then 3 + 11 = 14 is too much. Even the cheapest price left makes too much with 11, so 11 is in no pair: move on to the next most expensive. The two indices move toward each other.

Fig. 5. Each check rules out the cheapest or the most expensive price that is left, until 4 and 9 make 13.

Each check rules out one price, so 6 prices need at most 5 checks instead of 15. This only works because the prices are in order; an unordered list must be sorted first.

Implementation

The songs are an array a[1] to a[n] and the ride is the limit T. The run of songs from l to r is a window, and s is its total. The window starts empty, with l = 1, and r goes from 1 to n:

1. Add: s += a[r].

2. Drop: while s > T, subtract a[l] from s and increase l by 1.

3. Record: the window from l to r fits, so update best with its length r - l + 1.

The program reads n and T, then the n elements, and prints best, the length of the longest window with sum at most T. Then it prints count, the number of windows that fit: the windows that end at r and start at l, l + 1, …, r all fit, so the record step adds r - l + 1. For the 8-song playlist the input is:

8 12
4 2 2 3 2 2 6 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long T;
    cin >> n >> T;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long s = 0;   // total of the window
    int l = 1;         // first element of the window
    int best = 0;      // longest window so far
    long long count = 0;   // only needed to count the windows that fit
    for (int r = 1; r <= n; r++) {
        // add
        s += a[r];
        // drop
        while (s > T) {
            s -= a[l];
            l++;
        }
        // record
        best = max(best, r - l + 1);
        count += r - l + 1;   // only needed to count the windows that fit
    }
    cout << best << '\n';
    cout << count << '\n';   // only needed to count the windows that fit
}

For the 8-song playlist the program prints 5 and then 26 = 1 + 2 + 3 + 4 + 4 + 5 + 3 + 4. When every element is larger than T, the drop step empties the window: l = r + 1, the length is 0, and the program prints 0.

The while sits inside the for, but each pass of the while moves l one place to the right, and l never moves back from 1 to at most n + 1. So r moves n times and l at most n times in the whole program, at most $2n$ moves, and the program runs in $O(n)$ time.

Pair with a given sum

The prices are a[1] < a[2] < ... < a[n] and the card is x. Start with l = 1 and r = n, and while l < r:

1. Compare: look at sum = a[l] + a[r].

2. Found: if sum == x, print the pair and stop.

3. Move: if sum < x, increase l; if it is more, decrease r.

If the loop ends, there is no pair. The program reads n and x, then the n prices in increasing order. For the gift card the input is:

6 13
1 3 4 6 9 11

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int l = 1, r = n;
    while (l < r) {
        // compare
        long long sum = a[l] + a[r];
        if (sum == x) {
            // found
            cout << a[l] << ' ' << a[r] << '\n';
            return 0;
        }
        // move
        if (sum < x) l++;
        else r--;
    }
    cout << "no pair\n";
}

Each check moves l or r one place closer, so there are at most n - 1 checks: $O(n)$, plus O(n \log n) if the prices have to be sorted first. When several pairs make x, the program prints the first one it meets: with a card of 15 it prints 4 and 11, though 6 and 9 also make 15.

Correctness proof

Take the moment after song $r$ is added and the drops are done. We claim that $l$ is the earliest first song whose run up to $r$ fits. So the window from $l$ to $r$ is the longest run that ends at $r$, and the best over all $r$ is the answer.

The window from $l$ to $r$ fits, because the drops stop only then. Now take a song $j$ before $l$. It was dropped at some earlier moment, when the window from $j$ to some r' \le r had a total over $T$. The run from $j$ to $r$ contains that window and possibly more songs. No length is negative, so its total is at least as large, and it is over $T$ too. No run that starts before $l$ and ends at $r$ fits.

Fig. 6. The bracketed run, songs 4 to 7, takes 13 minutes.

For example, song 4 was dropped when the window from song 4 to song 7 took 3 + 2 + 2 + 6 = 13 minutes. Any run from song 1, 2, 3 or 4 to song 7 contains these four songs, so it takes at least 13 minutes and doesn't fit (Fig. 6).

The pair search never skips a pair. If a_l + a_r < x, then a_l plus any other price left is at most a_l + a_r, since a_r is the largest of them. So a_l is in no pair and can be skipped. If a_l + a_r > x, then a_r plus any price left is at least a_l + a_r, so a_r is in no pair.

Negative numbers

The proof needs a longer run never to have a smaller total, and that holds only when no number is negative. Take the array 4, −3, 2 and T = 3. The whole array sums to 3, so the answer is 3. The program adds 4, sees 4 > 3 and drops it at once, then adds −3 and 2 and prints 2. Dropping the 4 lowered the total, but adding −3 would have lowered it too, so the run from the 4 could still become good.

Common mistakes

• Resetting $r$ for each $l$ (r = l, or an inner for from $l$), which is correct but O(n^2), as in Fig. 3. Let $r$ only move forward.

• Pair search on an unsorted list, which can answer "no pair" when there is one. Sort first, and if the problem asks for the original positions, sort pairs (price, position).

• Using one item twice by writing while (l <= r), so that when l and r meet the search adds a price to itself. Write while (l < r).

Similar techniques

Binary search finds one partner in a sorted array in O(\log n). To find a partner for every element of a sorted array, $n$ binary searches take O(n \log n). If each partner is never to the left of the previous one, one forward-moving index finds them all in $O(n)$.

Prefix sums give the sum of any given window in $O(1)$, for any numbers, but they don't find the best window by themselves. Problems with negative numbers start from prefix sums and need more on top.

Sorting comes first in many two pointers problems: the pair search, and windows like "largest group whose maximum and minimum differ by at most $d$", which become runs in a row only after sorting.

A deque gives the minimum or maximum of every window of a fixed length. The window moves the same way, but the deque keeps the candidates for the minimum.

A map counts how many times each value is in the window, for rules like "no value twice": drop from the front while the new value is already in the window.

Three numbers with a given sum take O(n^2): fix one number and run the pair search on the rest.

Practice