Two Pointers and Sliding Window

Use monotone indices and maintained window state to replace many quadratic scans with linear passes.

Est. 90 min Updated Suggest a fix
💡 Note
Prerequisites: arrays and strings (Lessons 3–4), complexity analysis (Lesson 2), and basic loops. The code uses C arrays and indices.

What you will learn

By the end, you can recognise when two indices can eliminate repeated work, state the invariant that makes pointer movement safe, and distinguish a fixed-size window from a variable-size window. We will build from sorted pair search to a maximum-sum window and then a minimum-length positive-sum window.

🎯 Pro Tip
The Interview Problem-Solving Patterns unit already collects interview prompts and dry runs. This lesson teaches the underlying techniques; continue with Interview Problem-Solving Patterns → for practice sets instead of repeating them here.

1. Two pointers: preserve an invariant

Two pointers are two indices that move through a sequence according to a rule. The useful question is not simply “can I use two indices?” but “what fact lets me discard all candidates between or beyond them?” A sorted array gives that fact: if the smallest remaining value plus the largest is too small, pairing the smallest with anything else cannot reach the target, so the left index can advance.

Pair sum in a sorted array · C
#include <stdbool.h>

bool has_pair_sum(const int values[], int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        long long sum = (long long)values[left] + values[right];
        if (sum == target) return true;
        if (sum < target) left++;
        else right--;
    }
    return false;
}

For values [1, 2, 4, 6, 10] and target 8, the first sum is 11, so discard 10. The next is 7, so discard 1. Then 2 + 6 is 8. Each move rules out at least one endpoint, so the scan is O(n) time and O(1) extra space. The cast widens the addition before it happens, guarding against overflow when two int values are added.

2. Opposite-direction and same-direction pointers

Opposite-direction pointers often start at both ends: palindrome checks, reversing in place, or two-sum on sorted data. Same-direction pointers include slow/fast scans and the left/right boundaries of a window. Pointer names should describe their role, not just their speed: left is the start of the active range and right is the newly included element.

Palindrome check for a plain byte string · C
#include <stdbool.h>
#include <string.h>

bool is_palindrome(const char text[]) {
    size_t left = 0;
    size_t right = strlen(text);
    if (right == 0) return true;
    right--;
    while (left < right) {
        if (text[left] != text[right]) return false;
        left++;
        right--;
    }
    return true;
}

This example compares bytes exactly; it does not ignore spaces, punctuation, or letter case. That is a deliberate contract. “Palindrome” requirements vary, so normalisation (lowercasing, filtering characters, or Unicode handling) must be specified and performed separately when required. For empty input, returning true is consistent with the usual definition that no pair contradicts the palindrome property.

3. Sliding windows: a range with maintained state

A sliding window is a contiguous range [left, right]. Instead of recomputing a property for every range, add the new right element and remove elements from the left as the rule requires. For a fixed window of size k, each shift removes one value and adds one. The total work after initialization is O(n), not O(nk).

Maximum sum of a fixed-size window · C
#include <stdbool.h>
#include <stddef.h>

bool max_window_sum(const int values[], int n, int k, long long *answer) {
    if (answer == NULL || k <= 0 || k > n) return false;
    long long window_sum = 0;
    for (int i = 0; i < k; i++) window_sum += values[i];
    *answer = window_sum;
    for (int right = k; right < n; right++) {
        window_sum += values[right];
        window_sum -= values[right - k];
        if (window_sum > *answer) *answer = window_sum;
    }
    return true;
}

The invariant is that immediately before evaluating a candidate, window_sum equals the sum of exactly k elements ending at right. Using long long for the running total avoids assuming that many valid int values still fit in an int sum. For k equal to n, the initialization is the only candidate; for k outside 1…n, the function reports invalid input.

4. Variable windows and the condition that matters

A variable window grows by advancing right and shrinks by advancing left. The common minimum-length-subarray pattern is correct when values are non-negative (strictly positive is a common simpler contract). Adding a new value can only increase the sum, and removing a value can only decrease it. That monotonicity means shrinking after the sum reaches the target cannot hide a shorter valid window.

Shortest subarray with sum at least target (positive values) · C
#include <stdbool.h>
#include <limits.h>
#include <stddef.h>

bool min_length_at_least(const int values[], int n, long long target, int *length_out) {
    if (target <= 0 || length_out == NULL) return false;
    int left = 0;
    int best = INT_MAX;
    long long sum = 0;
    for (int right = 0; right < n; right++) {
        sum += values[right];
        while (sum >= target) {
            int length = right - left + 1;
            if (length < best) best = length;
            sum -= values[left++];
        }
    }
    if (best == INT_MAX) return false;
    *length_out = best;
    return true;
}

Both indices only move forward. Although there is a nested while, each element enters once and leaves at most once, so total work is O(n). This API requires a positive target and a non-null output pointer. Negative values break the monotonicity: removing a negative number can increase a sum. For arbitrary signed values, use a different technique such as prefix sums with a monotonic deque; do not apply this window rule blindly.

5. Choose the pattern from the input constraints

SignalTechniqueInvariant / requirementTypical cost
Sorted input; pair from both endsOpposite pointersEvery move rules out candidates using sorted orderO(n), O(1) extra
Contiguous range of exactly kFixed windowState describes the current k valuesO(n), O(1) extra
Longest/shortest range with monotone constraintVariable windowExpanding and shrinking changes validity predictablyUsually O(n), O(1) or O(k)
Need all pairs without sorted orderHashing or sort + pointersChoose based on output, duplicates, and mutation rulesOften O(n) or O(n log n)
📌 Real World Example
For a delivery app, “largest number of orders in any 15-minute interval” is a fixed-window count if events are bucketed uniformly. “Shortest contiguous period reaching a cumulative target” is a variable window only if the increments are non-negative. State the modelling assumption before choosing the algorithm.

6. Common mistakes

  • Using two pointers on unsorted data: pointer moves may discard valid answers. Sort only if reordering is allowed, or retain original indices; otherwise choose hashing or another method.
  • Updating the answer before the window is valid: first establish the invariant and verify the constraints at each point where the result is recorded.
  • Applying positive-window logic to negative values: the expand/shrink monotonicity disappears. Use prefix sums or another suitable structure.
  • Off-by-one boundaries: decide whether your range is inclusive or half-open. Here it is inclusive, so length is right - left + 1; empty input needs separate handling.

7. Practice

  1. Return the pair of indices (not values) for a sorted array. Explain how duplicate values affect whether there may be multiple answers.
  2. Given a string, determine whether it is a palindrome after ignoring ASCII whitespace and case. Separate normalisation from the two-pointer scan.
  3. Find the average of every contiguous window of size k in one pass. What is the running sum invariant?
  4. Find the longest substring with at most two distinct characters. Describe the frequency-map state and when to shrink.
  5. Test the minimum-length positive-window function with an impossible target, one element, target met exactly, and an invalid negative value.

Review checklist: Can you state why a pointer move is safe? Does every index advance only O(n) times? Are duplicates, empty input, overflow, and negative values covered by the problem contract?

🎯 Key Takeaways

  • ✓Two pointers work because an invariant makes discarded candidates impossible.
  • ✓A sliding window tracks a contiguous range and updates its state incrementally.
  • ✓Fixed-size windows add one item and remove one item per step.
  • ✓Variable windows need monotonicity; negative values often invalidate the simple shrink rule.
  • ✓Inclusive window length is right − left + 1; boundary contracts must be explicit.
  • ✓The Interview Problem-Solving Patterns unit provides separate interview drills for these techniques.

Next

Continue to binary-level operations, or revisit the sequence if you want to strengthen your range-query structures.

Lesson 26 · Bit Manipulation →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...