Two pointers and sliding windows

Many problems ask about pairs or ranges of an array. Trying every pair is O(n²). If the array is sorted, or the range can grow and shrink, two indexes that only move forward do it in O(n).

A pair with a given sum

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

int main() {
    vector<int> a = {1, 3, 4, 6, 8, 11};
    int target = 14;
    int i = 0, j = a.size() - 1;
    while (i < j) {
        int s = a[i] + a[j];
        if (s == target) break;
        if (s < target) i++;
        else j--;
    }
    if (i < j) cout << a[i] << " + " << a[j] << " = " << target << "\n";
    else cout << "no pair\n";
    return 0;
}

In a sorted array, start i at the left and j at the right. If a[i] + a[j] is too small, only moving i right can increase it; if too large, only moving j left can decrease it. Each step moves one index, so there are at most n steps. Watch i and j close in.

A sliding window

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

int main() {
    vector<int> a = {2, 1, 5, 1, 3, 2};
    int k = 3;
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int i = k; i < (int)a.size(); i++) {
        sum += a[i] - a[i - k];   // the new item in, the oldest out
        if (sum > best) best = sum;
    }
    cout << "best sum of " << k << " in a row: " << best << "\n";
    return 0;
}

For "the largest sum of k numbers in a row", keep the sum of the current window of k items. Moving the window one place adds the new item and subtracts the one that left: O(1) per move instead of re-adding k numbers.

Windows can also grow and shrink: "the shortest range whose sum is at least S" moves the right end forward, and the left end forward while the sum is still big enough. Both ends move at most n times.

Mark lesson complete