Two pointers and sliding windows

Many "check every pair" or "check every subarray" problems have an O(n²) brute force and an O(n) solution with two indices that only ever move forward. The total work is bounded by how far the indices can travel — at most n each — not by the number of pairs. The skill is knowing why a pointer is allowed to move without ever coming back, and writing that reason down as an invariant.

Three shapes cover most problems:

1. Opposite ends: pair with a target sum

Given sorted v, find i < j with v[i] + v[j] == target. Start with the widest pair and move one end at a time:

#include <optional>
#include <print>
#include <span>
#include <utility>
#include <vector>

std::optional<std::pair<std::size_t, std::size_t>> pair_with_sum(std::span<const int> v, long long target) {
    if (v.size() < 2) return std::nullopt;
    std::size_t i = 0, j = v.size() - 1;
    while (i < j) {
        long long s = static_cast<long long>(v[i]) + v[j];   // no int overflow
        if (s == target) return std::pair{i, j};
        if (s < target) ++i;    // v[i] + (anything left of j) is too small: v[i] is useless
        else            --j;    // v[j] + (anything right of i) is too big:  v[j] is useless
    }
    return std::nullopt;
}

int main() {
    std::vector<int> v{1, 3, 4, 6, 8, 11};
    if (auto p = pair_with_sum(v, 14)) std::println("{} + {} at [{}, {}]", v[p->first], v[p->second], p->first, p->second);
    std::println("found 2? {}", pair_with_sum(v, 2).has_value());
}

Why it's correct — the elimination argument. Invariant: no valid pair uses an index outside [i, j]. If v[i] + v[j] < target, then for every k ≤ j, v[i] + v[k] ≤ v[i] + v[j] < target (sorted), so v[i] can't be part of any remaining pair — discard it with ++i. Symmetrically for --j. Each step discards one index forever, so there are at most n − 1 steps.

Two traps: the sum of two ints can overflow (compute in long long), and the method needs sorted input — on unsorted data, use a hash set instead.

2. Fast / slow: compacting in place

read visits every element; write is where the next kept element goes. Everything in [0, write) is the answer so far.

#include <print>
#include <span>
#include <vector>

// Removes adjacent duplicates from sorted v; returns the new length.
std::size_t dedupe_sorted(std::span<int> v) {
    if (v.empty()) return 0;
    std::size_t write = 1;                       // v[0] is always kept
    for (std::size_t read = 1; read < v.size(); ++read)
        if (v[read] != v[write - 1])             // differs from the last kept value
            v[write++] = v[read];
    return write;
}

int main() {
    std::vector<int> v{1, 1, 2, 3, 3, 3, 7};
    std::size_t n = dedupe_sorted(v);
    v.resize(n);                                 // the tail is leftovers; drop it
    std::println("{}", v);
}

write ≤ read always, so writing never clobbers an unread element. This is exactly what std::remove, std::remove_if and std::unique do: they don't shrink the container — they compact the kept elements to the front and return the new logical end. The elements after it are valid but unspecified. That's why the classic idiom is erase-remove, and why C++20 added std::erase / std::erase_if, which do both steps:

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 2, 4};
    auto end = std::remove(v.begin(), v.end(), 2);
    std::println("size {} kept {}", v.size(), end - v.begin());   // size 5, kept 3
    v.erase(end, v.end());
    std::println("{}", v);

    std::vector<int> w{1, 2, 3, 2, 4};
    std::erase(w, 2);                                              // C++20: one call
    std::println("{}", w);
}

3. Sliding windows: grow on the right, shrink on the left

A variable-size window works when the condition is monotone in the window: if a window is valid, every smaller window inside it is valid too (or, for "at least" conditions, every larger one). Then:

• move hi right one step to take in a new element;
• while the window breaks the condition (or, for "shortest", while it still satisfies it), move lo right;
• record the answer at the right moment.

Worked example: shortest subarray with sum ≥ target

All values positive, so growing the window increases the sum and shrinking decreases it — the condition is monotone.

#include <print>
#include <span>
#include <vector>

// Length of the shortest subarray with sum >= target (values > 0); 0 if none.
std::size_t shortest_sum_at_least(std::span<const int> v, long long target) {
    std::size_t best = 0, lo = 0;
    long long sum = 0;                                  // sum of v[lo..hi]
    for (std::size_t hi = 0; hi < v.size(); ++hi) {
        sum += v[hi];
        while (sum >= target) {                         // valid: record, then try shorter
            std::size_t len = hi + 1 - lo;
            if (best == 0 || len < best) best = len;
            sum -= v[lo++];
        }
    }
    return best;
}

int main() {
    std::vector<int> v{2, 3, 1, 2, 4, 3};
    std::println("{}", shortest_sum_at_least(v, 7));   // 2: [4, 3]
    std::println("{}", shortest_sum_at_least(v, 100)); // 0: impossible
}

Why it's O(n) even with a loop inside a loop. hi advances n times in total, and lo advances at most n times in total — it never moves back. So the inner while body runs at most n times across the whole function, not per iteration. This is amortized analysis: count the total distance the pointers travel, not the iterations of each loop separately.

If values could be negative, adding an element might decrease the sum, the condition stops being monotone, and the window technique gives wrong answers. (That problem needs prefix sums plus a monotonic deque.)

Faded example: longest window with at most k distinct values

Here the condition "at most k distinct values" is valid for every sub-window of a valid window, so we shrink only while it's broken, and record the answer after the window is valid again. Fill in the shrink step:

std::unordered_map<int, std::size_t> count;    // value -> occurrences in window
std::size_t best = 0, lo = 0;
for (std::size_t hi = 0; hi < v.size(); ++hi) {
    ++count[v[hi]];
    while (count.size() > k) {
        /* ??? remove v[lo] from the window */
    }
    best = std::max(best, hi + 1 - lo);
}

if (--count[v[lo]] == 0) count.erase(v[lo]);
++lo;

Fixed-size windows

When the window size is fixed at w, add the incoming element and remove the outgoing one each step — O(1) per step instead of re-summing w elements:

#include <print>
#include <vector>

int main() {
    std::vector<int> v{2, 1, 5, 1, 3, 2};
    const std::size_t w = 3;
    long long sum = 0;
    for (std::size_t i = 0; i < v.size(); ++i) {
        sum += v[i];                          // element entering
        if (i >= w) sum -= v[i - w];          // element leaving
        if (i + 1 >= w) std::print("{} ", sum);
    }
    std::println();                           // 8 7 9 6
}

4. Choosing the counts structure

Windows over values usually need "how many of each value are inside". For small known alphabets (bytes, lowercase letters) use a std::array<int, 256> plus a separate distinct-counter — no hashing, no allocation. For arbitrary ints use std::unordered_map<int, std::size_t> and erase entries that hit zero, so size() stays meaningful.

Summary

• Two pointers turn O(n²) pair/subarray searches into O(n) when each pointer only moves forward and there's an argument for why it never needs to go back.
• Opposite ends on sorted data: move the end that can't be part of any answer.
• Fast/slow: [0, write) is the kept prefix; this is std::remove's contract (it doesn't shrink — erase afterwards, or use std::erase).
• Sliding window needs a monotone condition. Grow with hi, shrink with lo in a while, and the total cost is O(n) because lo travels at most n.
• Compute sums in a wider type; erase zero counts from the map.