Chapter 3.4: Two Pointers & Sliding Window

📝 Before You Continue: You should be comfortable with arrays, vectors, and std::sort (Chapters 2.3–3.3). This technique requires a sorted array for the classic two-pointer approach.

Two pointers and sliding window are among the most elegant tricks in competitive programming. They transform naive O(N²) solutions into O(N) by exploiting monotonicity: as one pointer moves forward, the other never needs to go backward.

3.4.1 The Two Pointer Technique

The idea: maintain two indices, left and right, into a sorted array. Move them toward each other (or in the same direction) based on the current sum/window.

When to use:

• Finding a pair/triplet with a given sum in a sorted array
• Checking if a sorted array contains two elements with a specific relationship
• Problems where "if we can do X with window size k, we can do X with window size k-1"

The diagram shows how two pointers converge toward the center, each step eliminating an entire row/column of pairs from consideration.

Problem: Find All Pairs with Sum = Target

Naïve O(N²) approach:

// O(N²): check every pair
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            cout << arr[i] << " + " << arr[j] << "\n";
        }
    }
}

Two Pointer O(N) approach (requires sorted array):

// Solution: Two Pointer — O(N log N) for sort + O(N) for search
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    sort(arr.begin(), arr.end());  // MUST sort first

    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << arr[left] << " + " << arr[right] << " = " << target << "\n";
            left++;
            right--;  // advance both pointers
        } else if (sum < target) {
            left++;   // sum too small: move left pointer right (increase sum)
        } else {
            right--;  // sum too large: move right pointer left (decrease sum)
        }
    }

    return 0;
}

Why Does This Work?

Key insight: After sorting, if arr[left] + arr[right] < target, then no element smaller than arr[right] can pair with arr[left] to reach target. So we safely advance left.

Similarly, if the sum is too large, no element larger than arr[left] can pair with arr[right] to reach target. So we safely decrease right.

Each step eliminates at least one element from consideration → O(N) total steps.

Complete Trace

Array = [1, 2, 3, 4, 5, 6, 7, 8], target = 9:

State: left=0(1), right=7(8)
  sum = 1+8 = 9 ✓ → print (1,8), left++, right--

State: left=1(2), right=6(7)
  sum = 2+7 = 9 ✓ → print (2,7), left++, right--

State: left=2(3), right=5(6)
  sum = 3+6 = 9 ✓ → print (3,6), left++, right--

State: left=3(4), right=4(5)
  sum = 4+5 = 9 ✓ → print (4,5), left++, right--

State: left=4, right=3 → left >= right, STOP

All pairs: (1,8), (2,7), (3,6), (4,5)

3-Sum Extension

Finding a triplet that sums to target: fix one element, use two pointers for the remaining pair.

// O(N²) — much better than O(N³) brute force
sort(arr.begin(), arr.end());
for (int i = 0; i < n - 2; i++) {
    int left = i + 1, right = n - 1;
    while (left < right) {
        int sum = arr[i] + arr[left] + arr[right];
        if (sum == target) {
            cout << arr[i] << " " << arr[left] << " " << arr[right] << "\n";
            left++; right--;
        } else if (sum < target) left++;
        else right--;
    }
}

3.4.2 Sliding Window — Fixed Size

A sliding window of fixed size K moves across an array, maintaining a running aggregate (sum, max, count of distinct, etc.).

Problem: Find the maximum sum of any contiguous subarray of size K.

Array: [2, 1, 5, 1, 3, 2], K=3
Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
Answer: 9

Naïve O(NK): Compute sum from scratch for each window.

Sliding window O(N): Add the new element entering the window, subtract the element leaving.

// Solution: Sliding Window Fixed Size — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    // Compute sum of first window
    long long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];

    long long maxSum = windowSum;

    // Slide the window: add arr[i], remove arr[i-k]
    for (int i = k; i < n; i++) {
        windowSum += arr[i];        // new element enters window
        windowSum -= arr[i - k];   // old element leaves window
        maxSum = max(maxSum, windowSum);
    }

    cout << maxSum << "\n";
    return 0;
}

Trace for [2, 1, 5, 1, 3, 2], K=3:

Initial window [2,1,5]: sum=8, max=8
i=3: add 1, remove 2 → sum=7, max=8
i=4: add 3, remove 1 → sum=9, max=9
i=5: add 2, remove 5 → sum=6, max=9
Answer: 9 ✓

3.4.3 Sliding Window — Variable Size

The most powerful variant: the window expands when we need more, and shrinks when a constraint is violated.

Problem: Find the smallest contiguous subarray with sum ≥ target.

// Solution: Variable Window — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    int left = 0;
    long long windowSum = 0;
    int minLen = INT_MAX;

    for (int right = 0; right < n; right++) {
        windowSum += arr[right];   // expand: add right element

        // Shrink window from left while constraint satisfied
        while (windowSum >= target) {
            minLen = min(minLen, right - left + 1);
            windowSum -= arr[left];
            left++;                // shrink: remove left element
        }
    }

    if (minLen == INT_MAX) cout << 0 << "\n";  // no such subarray
    else cout << minLen << "\n";

    return 0;
}

Why O(N)? Each element is added once (when right passes it) and removed at most once (when left passes it). Total operations: O(2N) = O(N).

Problem: Longest Subarray with At Most K Distinct Values

// Variable window: longest subarray with at most K distinct values
int left = 0, maxLen = 0;
map<int, int> freq;  // frequency of each value in window

for (int right = 0; right < n; right++) {
    freq[arr[right]]++;

    // Shrink while we have > k distinct values
    while ((int)freq.size() > k) {
        freq[arr[left]]--;
        if (freq[arr[left]] == 0) freq.erase(arr[left]);
        left++;
    }

    maxLen = max(maxLen, right - left + 1);
}
cout << maxLen << "\n";

3.4.4 USACO Example: Haybale Stacking

Problem (USACO 2012 November Bronze): N haybales in a line. M operations, each adds 1 to all bales in range [a, b]. How many bales have an odd number of additions at the end?

This is actually best solved with a difference array (Chapter 3.2), but a simpler version:

Problem: Given array of integers, find the longest subarray where all elements are ≥ K.

// Two pointer: longest contiguous subarray where all elements >= K
int left = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
    if (arr[right] < K) {
        left = right + 1;  // reset window: current element violates constraint
    } else {
        maxLen = max(maxLen, right - left + 1);
    }
}

⚠️ Common Mistakes

1. Not sorting before two-pointer: The two-pointer technique for pair sum only works on sorted arrays. Without sorting, you'll miss pairs or get wrong answers.
2. Moving both pointers when a pair is found: When you find a matching pair, you must move BOTH left++ AND right--. Moving only one misses some pairs (unless duplicates aren't relevant).
3. Off-by-one in window size: The window [left, right] has size right - left + 1, not right - left.
4. Forgetting to handle empty answer: For the "minimum subarray" problem, initialize minLen = INT_MAX and check if it changed before outputting.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Does two-pointer always require sorting?

A: Not necessarily. "Opposite-direction two pointers" (like pair sum) require sorting; "same-direction two pointers" (like sliding window) do not. The key is monotonicity — pointers only move in one direction.

Q2: Both sliding window and prefix sum can compute range sums — which to use?

A: For fixed-size window sum/max, sliding window is more intuitive. For arbitrary range queries, prefix sum is more general. Sliding window can only handle "continuously moving windows"; prefix sum can answer any [L,R] query.

Q3: Can sliding window handle both "longest subarray satisfying condition" and "shortest subarray satisfying condition"?

A: Both, but with slightly different logic. "Longest": expand right until condition fails, then shrink left until condition holds again. "Shortest": expand right until condition holds, then shrink left until it no longer holds, recording the minimum length throughout.

Q4: How does two-pointer handle duplicate elements?

A: Depends on the problem. If you want "all distinct pair values", after finding a pair do left++; right-- and skip duplicate values. If you want "count of all pairs", you need to carefully count duplicates (may require extra counting logic).

🔗 Connections to Later Chapters

• Chapter 3.2 (Prefix Sums): prefix sums and sliding window are complementary — prefix sums suit offline queries, sliding window suits online processing
• Chapter 3.3 (Sorting): sorting is a prerequisite for two pointers — opposite-direction two pointers require a sorted array
• Chapter 3.5 (Monotonic): monotonic deque can enhance sliding window — maintaining window min/max in O(N)
• Chapters 6.1–6.3 (DP): some problems (like LIS variants) can be optimized with two pointers

Practice Problems

Problem 3.4.1 — Pair Sum Count 🟢 Easy Given N integers and a target T, count the number of pairs (i < j) with arr[i] + arr[j] = T.

Problem 3.4.2 — Maximum Average Subarray 🟡 Medium Find the contiguous subarray of length exactly K with the maximum average. Print the average as a fraction or decimal.

Problem 3.4.3 — Minimum Window Covering 🔴 Hard Given string S and string T, find the shortest substring of S that contains all characters of T.

🏆 Challenge: USACO 2017 February Bronze — Why Did the Cow Cross the Road Given a grid with cows and their destinations, find which cow can reach its destination fastest. Use two-pointer / greedy on sorted intervals.