Two Pointers

22 Sep 2024

1. Introduction

Two pointers is a fundamental technique for arrays, strings, and contiguous-range problems. Two indices describe the current interval: the left pointer l and the right pointer r. The current window is [l, r].

The most common pattern moves the right pointer to expand the window. When the window no longer satisfies its condition, the left pointer moves right to shrink it. Since neither pointer ever moves backward, each element is added to the window at most once and removed at most once. The total time complexity is usually O(n), rather than O(n²) for enumerating every interval.

2. The Basic Pattern

Suppose a problem asks for a contiguous interval in an array that satisfies a condition. A two-pointer solution maintains this process:

Move the right pointer rightward, add the new element to the window, and update its information, such as the sum, number of elements, or a frequency count.
If the window becomes invalid, move the left pointer rightward until it is valid again, removing departing elements from the window information.
Whenever the window is valid, use it to update the answer.

The window information must be quick to update. For a range sum, adding a[r] on the right means sum += a[r]; removing a[l] on the left means sum -= a[l]. There is no need to scan the whole window again.

3. Example: The Longest Consecutive Range Within Time T

Given the reading time a[i] for each book and a total limit T, find the greatest number of consecutive books that can be read without exceeding T. The key is to maintain the total reading time, sum, for the current window.

After the right pointer adds a book, if sum > T, the window is too long. Keep removing the leftmost book until sum <= T. The resulting window [l, r] is valid, so its length can update the answer.

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

const int N = 1000000 + 10;
long long a[N];

int main() {
    int n;
    long long T;
    cin >> n >> T;

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

    int l = 1;
    int answer = 0;
    long long sum = 0;

    for (int r = 1; r <= n; r++) {
        sum += a[r];

        while (sum > T) {
            sum -= a[l];
            l++;
        }

        answer = max(answer, r - l + 1);
    }

    cout << answer;
    return 0;
}

For example, let the reading times be [3, 1, 2, 1, 4] and let T be 5.

When the right pointer reaches the third book, the window is [3, 1, 2] and its total is 6, which exceeds the limit.
Moving the left pointer removes the first book, leaving [1, 2] with a total of 3, so the window is valid again.
Continue moving the right pointer and update the maximum length whenever the window is valid.

The while loop may look nested, but the left pointer moves from 1 to n at most once in the entire program. Together, the two pointers make at most 2n moves, so the complexity remains O(n).

4. When It Applies

The range-sum pattern above requires non-negative array elements. Adding a non-negative value on the right can only increase sum, and removing one on the left can only decrease it. That monotonic behavior is what makes the window adjustment valid.

If the array can contain negative values, adding an element may decrease the sum and removing one may increase it. In that case, this simple two-pointer method is not necessarily correct.

The same window idea also applies to strings and category counts. For example, maintain the frequency of each character in a window; when the window contains every required character, shrink its left side to search for the shortest covering substring. If elements have no natural order, they can sometimes be sorted by value or coordinate first, then processed with two pointers.

5. Common Mistakes

Forgetting to update the window information immediately after adding the rightmost element.
Forgetting to remove the effect of a[l] from the sum or counter when shrinking from the left.
Using if instead of while; shrinking once may still leave the window invalid.
Miscalculating the window length. With one-based indices, it is r - l + 1.

The point of two pointers is not a fixed template. It is to maintain a window whose meaning is always clear: the right pointer tries to enlarge a candidate answer, while the left pointer restores validity when the condition is broken. Once the window condition and its maintained information are clear, many contiguous-range problems become a linear scan.

Two Pointers

Related Posts