STL algorithm patterns: two pointers, sliding windows, and prefix sums

Learning objectives

• Identify when sorted input makes a two-pointer scan appropriate.
• Use a sliding window only when its condition can be maintained as the window expands and shrinks.
• Build prefix sums to answer repeated range-sum queries.
• State the assumptions behind each pattern and derive its time and space costs.

Prerequisites: vectors, loops, iterators, sorting, and basic Big-O notation. The examples use C++17-compatible standard-library features.

Patterns help you recognize structure

Many programming problems are variations of a few patterns. A pattern is not a magic trick: it is a way to maintain a useful invariant while processing data. Choose one only after understanding the input constraints and expected output.

Two pointers

For a sorted vector, two pointers can find a pair that sums to a target in linear time.

bool has_pair(const std::vector<int>& a, int target) {
    std::size_t left = 0, right = a.size();
    if (a.size() < 2) return false;
    --right;
    while (left < right) {
        long long sum = static_cast<long long>(a[left]) + a[right];
        if (sum == target) return true;
        if (sum < target) ++left; else --right;
    }
    return false;
}

Each step discards a range that cannot contain a solution because the vector is sorted. Time complexity is O(n); extra space is O(1).

Sliding window

For non-negative values, the following window finds whether a contiguous range sums to a target. The non-negative assumption matters: with negative values, shrinking the window does not always reduce its sum.

bool has_sum(const std::vector<int>& a, long long target) {
    std::size_t left = 0;
    long long sum = 0;
    for (std::size_t right = 0; right < a.size(); ++right) {
        sum += a[right];
        while (left <= right && sum > target) sum -= a[left++];
        if (sum == target) return true;
    }
    return false;
}

Prefix sums

std::vector<long long> prefix(a.size() + 1, 0);
for (std::size_t i = 0; i < a.size(); ++i) prefix[i + 1] = prefix[i] + a[i];
// Sum of half-open range [left, right):
long long range_sum = prefix[right] - prefix[left];

Build prefix sums in O(n), then answer each range-sum query in O(1). Use a wide enough integer type to avoid overflow for the expected constraints.

Choose the pattern carefully

• Two pointers often benefit from sorted data or monotonic movement.
• Sliding windows suit contiguous ranges when the condition changes predictably as endpoints move.
• Prefix sums are useful when many range-sum queries share the same array.
• Frequency maps help count occurrences or track previously seen values.

Common mistakes

• Using two pointers on unsorted data when the algorithm depends on ordering.
• Applying a standard sliding window to negative values when the monotonic condition no longer holds.
• Building prefix sums with an element type that can overflow for the expected input bounds.
• Claiming O(n) without explaining why each pointer or index moves only a bounded number of times.

Practice

1. Why does the two-pointer pair-sum algorithm require sorted input?
2. Why does the shown sliding window require non-negative values?
3. How can a prefix array answer a range sum?

Summary

Learn the invariant behind each pattern, state assumptions explicitly, and analyze both time and space complexity. A pattern applied outside its assumptions can silently produce wrong answers.

References

• CP-Algorithms reference
• cppreference: algorithms library