Two Pointers & Sliding Window: Linear-Time Array and String Patterns

1. Introduction and Motivation

A large fraction of array and string interview problems ask some version of: find a pair, subarray, or substring that satisfies a condition. The brute-force answer is almost always the same shape — try every pair with a double loop, or try every contiguous slice with a double loop — and it is almost always $O(n^2)$ or worse. Two pointers and sliding window are the two techniques that most often collapse that double loop into a single $O(n)$ pass, not through a clever trick but by proving that most of the combinations the brute force checks were never candidates in the first place.

Two pointers uses a pair of indices that move through a sequence according to a rule tied to sortedness or to a running state (fast/slow). Sliding window uses a contiguous range, described by two boundaries, that grows and shrinks according to a rule tied to a running aggregate (a sum, a count, a set of characters). Both techniques share the same underlying idea: once you can prove that a move in one direction can only make things worse, you never need to undo that move.

2. Prerequisites

This lesson assumes comfort with basic array traversal, indexing, and in-place mutation — reading and writing A[i], swapping elements, and shrinking a logical length without resizing the underlying storage. If any of that feels shaky, review Part 3: Arrays & Array ADT Operations before continuing; several patterns below (same-direction pointers, partitioning) are direct extensions of the in-place array operations covered there.

You should also be comfortable with basic hash sets or hash maps for counting characters, and with $O$, $\Theta$, and $\Omega$ notation from algorithm analysis. No sorting algorithm internals are required, only the fact that a sorted array lets a comparison at the ends tell you something about every element in between.

3. A Concrete Example

Four steps found the pair, and the pointers only ever moved toward each other. No index was revisited, and no pair outside the shrinking [left, right] range was ever a candidate that got skipped incorrectly — the next section explains exactly why that is guaranteed, not lucky.

4. Core Insight

1. Identify what makes a move "safe": an order (sorted array), or a monotonic aggregate (a window sum, a character-frequency map).
2. Start the pointers or window boundaries at the extremes of the range you must search: both ends for opposite-direction pointers, or both at index 0 for a window.
3. Compute the current combination's value and compare it against the target condition.
4. If the combination overshoots the target, move the pointer or boundary that can only decrease the result. If it undershoots, move the one that can only increase it.
5. Never move a pointer backward once it has been proven that no valid answer could involve the positions it left behind.
6. Stop when the pointers cross (two pointers) or when the window boundary reaches the end of the sequence (sliding window).

5. Correctness: Why It Works

For opposite-direction two pointers on an ascending sorted array with left and right, the proof that a move never skips a valid answer rests on one fact: every value between left and right is bounded by the values already at left and right.

1. If A[left] + A[right] > target: for every remaining index l' with left ≤ l' ≤ right, sortedness gives A[l'] ≥ A[left], so A[l'] + A[right] ≥ A[left] + A[right] > target. The value at right is too large to pair with any remaining left candidate, so decrementing right discards no valid pair.
2. If A[left] + A[right] < target: symmetrically, for every remaining index r', A[left] + A[r'] ≤ A[left] + A[right] < target, so the value at left is too small to pair with any remaining right candidate. Incrementing left discards no valid pair.
3. If they are equal, the pair is found. Since each step strictly shrinks the range and every discard is proven safe, the algorithm terminates having examined every combination that could possibly be valid.

Sliding window correctness rests on a similar monotonicity argument, phrased over window feasibility rather than pair sums: if a window [l, r] already violates the required condition (a duplicate character, a sum too large), then any wider window [l', r] with l' < l contains that same violation, so it cannot be feasible either. That means once [l, r] becomes infeasible, the left boundary only ever needs to move forward to restore feasibility — it never needs to jump back past a position already ruled out, which is exactly why the total work across the whole scan stays linear.

6. Complexity Analysis

7. Three-Language Implementation

Each panel solves Container With Most Water: given a list of vertical line heights, find the two lines that, together with the x-axis, form the container that holds the most water. It is the cleanest showcase of opposite-direction two pointers, because the "move the shorter wall" rule follows directly from the correctness argument in Section 5 — the shorter of the two current walls caps every area it could form with any wall still between the pointers, so it can never be part of a better answer once a taller wall exists on the other side.

def max_area(height):
    if len(height) < 2:
        raise ValueError("max_area needs at least two heights")

    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        area = min(height[left], height[right]) * width
        best = max(best, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

sample = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print("Max area:", max_area(sample))  # Max area: 49

#include <iostream>
#include <stdexcept>
#include <vector>
#include <algorithm>

int max_area(const std::vector<int>& height) {
    if (height.size() < 2) {
        throw std::invalid_argument("max_area needs at least two heights");
    }
    std::size_t left = 0, right = height.size() - 1;
    int best = 0;
    while (left < right) {
        int width = static_cast<int>(right - left);
        int area = std::min(height[left], height[right]) * width;
        best = std::max(best, area);
        if (height[left] < height[right]) {
            ++left;
        } else {
            --right;
        }
    }
    return best;
}

int main() {
    std::vector<int> sample{1, 8, 6, 2, 5, 4, 8, 3, 7};
    std::cout << "Max area: " << max_area(sample) << '\n';
}

import java.util.List;

public class ContainerWithMostWater {
    static int maxArea(List<Integer> height) {
        if (height.size() < 2) {
            throw new IllegalArgumentException("maxArea needs at least two heights");
        }
        int left = 0, right = height.size() - 1;
        int best = 0;
        while (left < right) {
            int width = right - left;
            int area = Math.min(height.get(left), height.get(right)) * width;
            best = Math.max(best, area);
            if (height.get(left) < height.get(right)) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        List<Integer> sample = List.of(1, 8, 6, 2, 5, 4, 8, 3, 7);
        System.out.println("Max area: " + maxArea(sample)); // Max area: 49
    }
}

8. Pattern Deep Dives

Opposite-Direction Two Pointers

The worked example in Section 3 is the canonical case: pair sum in a sorted array (LeetCode calls this Two Sum II). Two pointers start at the ends and close inward using exactly the rule proven safe in Section 5. The same shape solves Container With Most Water, implemented in full above — both problems shrink a range from the outside in, guided by which side is provably not part of a better answer.

The pattern generalizes to any problem where a sorted order lets you bound an entire remaining range with a single comparison at its edge: closest pair to a target, counting pairs with sum below a threshold, and partition-style checks on sorted input all reuse this same two-line loop body.

Same-Direction (Fast/Slow) Two Pointers

Here both pointers move forward, but at different rates or with a gap, over an array that need not be sorted. Remove duplicates in place from a sorted array keeps a "write" pointer just behind a "read" pointer:

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write  # nums[:write] holds the deduplicated prefix

Move zeroes to the end while preserving the relative order of non-zero elements uses the same write/read shape, just with a different predicate:

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

Partitioning (as in the Dutch national flag problem, or the partition step of quicksort) is the three-way generalization: a low boundary, a high boundary, and a scanning pointer that swaps elements into the correct region as it advances, never revisiting a position once it has been classified.

The same fast/slow idea, applied to a linked list instead of an array, is how you detect a cycle: a slow pointer advancing one node at a time and a fast pointer advancing two nodes at a time will meet if and only if the list loops back on itself. That derivation belongs to linked lists rather than arrays, so it is not repeated here — see Floyd's Cycle Detection in the Linked Lists guide for the full proof and code.

3-Sum / 4-Sum Pattern

3-Sum asks for every triple of distinct elements that sums to a target (commonly zero). Sort the array, fix one element with an outer loop, and run the opposite-direction two-pointer scan from Section 5 over the rest to find the remaining pair — turning an $O(n^3)$ triple loop into $O(n^2)$:

def three_sum(nums):
    nums.sort()
    triples = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicate anchors
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triples.append((nums[i], nums[left], nums[right]))
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1  # skip duplicate pairs
    return triples

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [(-1, -1, 2), (-1, 0, 1)]

4-Sum extends the same idea with a second fixed outer index, giving $O(n^3)$: fix two elements, then two-pointer scan the rest. In general, $k$-Sum fixes $k-2$ elements and finishes with one $O(n)$ two-pointer pass, for $O(n^{k-1})$ total after sorting.

Fixed-Size Sliding Window

When the window width is a known constant $k$, maintain a running sum (or other aggregate) and slide by one position at a time: add the entering element, remove the leaving element, never rescan the whole window.

def max_sum_subarray(nums, k):
    if len(nums) < k:
        raise ValueError("array shorter than window size")

    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9  (5 + 1 + 3)

The window's left edge is implicit — it is always exactly $k$ behind the right edge — so there is only one moving boundary to reason about.

Variable-Size Sliding Window

Longest substring without repeating characters grows the right boundary greedily and shrinks the left boundary only when the feasibility condition (no repeated character in the window) breaks, using the monotonicity argument from Section 5:

def longest_unique_substring(s):
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1  # shrink past the earlier occurrence
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring("abcabcbb"))  # 3  ("abc")

Minimum window substring flips the growth direction: expand the right boundary until the window contains every required character (with multiplicity), then shrink the left boundary as far as possible while the window still qualifies, recording the smallest qualifying window seen:

from collections import Counter

def min_window_substring(s, t):
    if not t:
        return ""
    need = Counter(t)
    missing = len(t)
    left = 0
    best_left, best_len = 0, float("inf")

    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        while missing == 0:
            if right - left + 1 < best_len:
                best_left, best_len = left, right - left + 1
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return "" if best_len == float("inf") else s[best_left:best_left + best_len]

print(min_window_substring("ADOBECODEBANC", "ABC"))  # "BANC"

Both problems share one loop shape: an outer pass that only ever advances right, and an inner while that advances left whenever the current window is either invalid (too many repeats) or already better than it needs to be (still satisfies the requirement). Total pointer movement across both loops is bounded by $2n$, which is why the whole scan is $O(n)$ even though it looks like nested loops.

Sliding Window Maximum (preview)

Now ask for the maximum of every window of size $k$ as it slides across the array, not just one running sum. The naive approach recomputes the maximum of each window from scratch:

def max_sliding_window_naive(nums, k):
    return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

This is correct but costs $O(nk)$: for each of the roughly $n$ window positions, scanning the $k$ elements inside it throws away the ordering information the previous window already established about most of those same elements. That repeated, discardable work is the same pattern-recognition signal you have seen throughout this lesson — a sign that a smarter data structure can remember what plain pointers cannot. The $O(n)$ solution keeps a monotonic deque of candidate maximums instead of rescanning, and that structure and its proof are covered in depth in the Monotonic Stacks, Queues & Histogram Problems lesson. This lesson stops at recognizing the naive bound and why it is too slow; the deque mechanics live there.

9. Applications and Alternatives

Two pointers is not always the right tool. If the input is not sorted and cannot be sorted (order matters, or sorting costs more than the savings), a hash set or hash map often solves the same pair-sum problem in $O(n)$ time and $O(n)$ space instead of $O(n \log n)$ time and $O(1)$ space — a straightforward time/space tradeoff. If a window needs an order statistic such as a running median rather than a sum or count, a pair of heaps (or a balanced structure) replaces the simple window state. And if a window needs its running maximum or minimum rather than a sum, plain pointers are insufficient on their own; that is exactly the gap the monotonic deque referenced in Section 8 fills.

10. Exercises and Mastery

Easy

1. Given a sorted array and a target, return the 1-indexed positions of the two numbers that sum to the target using $O(1)$ extra space (Two Sum II).

Medium

1. Given a string, return the length of the longest substring that contains no repeating characters, and state why your left boundary never needs to move backward.

Hard

1. Given strings s and t, return the smallest substring of s that contains every character of t, including repeated characters, or an empty string if no such window exists (Minimum Window Substring).

Review rhythm: tomorrow, redo the pair-sum proof from Section 5 without notes; next week, implement the longest-unique-substring and minimum-window-substring solutions again from a blank file and compare them line by line against the versions above; several weeks later, solve a new problem you have not seen before by first asking whether it is opposite-direction, same-direction, fixed-window, or variable-window before writing any code.

11. Summary Cheat Sheet

• Two pointers and sliding window both replace a brute-force nested loop by proving that most combinations it checks are already dead ends.
• Opposite-direction pointers need a sorted order; the edge comparison bounds an entire remaining range in one step.
• Same-direction (fast/slow) pointers need no sorting; they compact or classify an array in place, and the same idea detects cycles in linked lists.
• 3-Sum and 4-Sum are an outer loop over fixed elements plus an inner two-pointer scan: $O(n^2)$ and $O(n^3)$ respectively after sorting.
• Fixed windows track a running aggregate over a constant-width slice; variable windows grow greedily and shrink only when feasibility breaks.
• Sliding window maximum needs more than plain pointers — recognize the naive $O(nk)$ bound and move on to a monotonic deque for $O(n)$.
• Both families are $O(n)$ time and $O(1)$ or $O(k)$ extra space, which is exactly what makes them the default answer once brute force has been named and rejected.