Two-Pointer & Sliding Window — Use two-pointer and sliding window patterns with arrays/strings (intro) - C Plus Plus

SECTION 1

Historical Context & Motivation

The idea of maintaining multiple index variables to traverse a data structure is nearly as old as imperative programming itself, but the formal recognition of the two-pointer technique and the sliding window pattern as named algorithmic strategies evolved gradually. Early sorting and searching algorithms—merge sort's merge step in the 1940s, for instance—implicitly used two pointers walking through separate arrays. As competitive programming communities and technical interview culture grew in the 2000s, these patterns were codified, named, and taught as first-class problem-solving tools that convert naïve O(n²) approaches into elegant O(n) solutions.

1945 • Von Neumann's Merge Sort

John von Neumann describes merge sort, whose merge step uses two pointers advancing through sorted sub-arrays—one of the earliest implicit uses of the two-pointer paradigm in algorithm design.

1959 • Partition in Quicksort

Tony Hoare's quicksort partition scheme uses two pointers converging from opposite ends of an array toward a pivot, establishing the converging two-pointer pattern that remains foundational today.

1976 • Floyd's Cycle Detection

Robert Floyd publishes the tortoise-and-hare algorithm for cycle detection in linked lists, a landmark application of two pointers moving at different speeds through a sequence.

2003 • Competitive Programming Codification

Online judges such as SPOJ and TopCoder popularize named patterns including 'sliding window' and 'two pointers,' making them standard vocabulary for algorithmic problem solving and interview preparation.

2015+ • LeetCode Era & Pattern Catalogs

Platforms like LeetCode and curated lists such as 'Blind 75' formalize two-pointer and sliding window as essential categories, with hundreds of tagged problems driving widespread adoption in CS curricula.

The central question these patterns address is deceptively simple: given a contiguous sequence of elements, how can we examine all relevant sub-sequences or pairs without resorting to nested loops? The answer—carefully advancing one or two index variables according to well-defined invariants—turns out to be remarkably powerful, reducing time complexity from quadratic to linear in a wide class of problems involving sorted arrays, substring constraints, and contiguous subarray aggregation.

SECTION 2

Core Principles & Definitions

Both the two-pointer and sliding window patterns share a fundamental insight: by maintaining state that evolves incrementally as pointers advance, we avoid redundant computation. Each element is visited a bounded number of times—typically once or twice—yielding amortized linear time. Understanding the distinctions and commonalities between these two closely related strategies is essential before applying them to concrete problems.

Two-Pointer (Opposite Direction)

Place one pointer at the start and another at the end of a sorted array. Move them toward each other based on a comparison condition (e.g., checking if a pair sums to a target). The sorted order guarantees that advancing one pointer monotonically changes the aggregate value.

Two-Pointer (Same Direction)

Both pointers start at the beginning and advance in the same direction, often at different speeds or under different conditions. The classic slow/fast pointer paradigm—used in removing duplicates in-place or detecting cycles—falls into this category.

Fixed-Size Sliding Window

Maintain a window of exactly k elements. Slide it rightward one position at a time, adding the incoming element and removing the outgoing one. This computes every k-length subarray aggregate in O(n) by reusing the previous window's result.

Variable-Size Sliding Window

Expand the window's right boundary until a constraint is violated, then shrink from the left until the constraint is restored. This finds the optimal subarray or substring satisfying a condition—e.g., the longest substring with at most k distinct characters.

Loop Invariant Discipline

Every two-pointer or sliding window algorithm relies on a carefully stated invariant that holds at the start of each iteration. The invariant guides which pointer to advance and proves correctness—without it, subtle off-by-one and missed-case bugs proliferate.

✦

KEY TAKEAWAY

Think of the two-pointer technique like two people standing at opposite ends of a bookshelf looking for a specific pair of books whose combined page count matches a target. Instead of having one person walk the entire shelf for every book the other picks up (O(n²)), they communicate: if the current pair's total is too large, the person on the right steps inward; if too small, the person on the left steps inward. They meet in the middle having checked only O(n) pairs. The sliding window is like dragging a magnifying glass across a line of text—you add a character on the right edge and drop one from the left, never re-reading the entire visible portion.

SECTION 3

Visual Explanation — Two-Pointer on a Sorted Array

The diagram traces a two-pointer search for a pair summing to 11 in the sorted array [1, 3, 5, 7, 8, 9, 12]. The left pointer (L) starts at index 0 and the right pointer (R) starts at index 6. Each iteration compares the sum to the target and advances the appropriate pointer. After only four comparisons, the pair (3, 8) is found.

The critical observation driving this diagram is that the sorted order creates a monotonic relationship between pointer movement and the resulting sum. Moving the left pointer rightward can only increase the sum, while moving the right pointer leftward can only decrease it. This monotonicity guarantees that we never need to revisit a pointer position—each element is examined at most once by each pointer, yielding the O(n) time complexity that distinguishes the technique from a brute-force O(n²) nested scan. In C++, this translates to a clean while (left < right) loop with at most n iterations.

SECTION 4

How It Works — Complexity Analysis & Invariants

To rigorously understand why these patterns achieve linear time, we need to examine the amortized cost of pointer advances. Both the two-pointer and sliding window techniques rely on the fact that the total number of pointer increments across all iterations is bounded by O(n), even though individual iterations may appear to do variable amounts of work.

TWO-POINTER TIME COMPLEXITY

T(n) = O(left_advances + right_advances) ≤ O(n + n) = O(n)

Each pointer starts at one extreme and moves monotonically toward the other. The left pointer advances at most n times total, and the right pointer advances at most n times total. Since each pointer only moves forward (or backward), the combined work is at most 2n steps.

FIXED-SIZE WINDOW RECURRENCE

window_sum(i) = window_sum(i−1) + a[i+k−1] − a[i−1]

Where a is the array, k is the window size, and i is the window's left index. Each slide adds the new right element and subtracts the departing left element, achieving O(1) per slide and O(n) overall.

VARIABLE-SIZE WINDOW — AMORTIZED ANALYSIS

T(n) = Σ(expand_cost + shrink_cost) ≤ O(n + n) = O(n)

The right pointer expands at most n times total across all iterations. The left pointer shrinks at most n times total (it can never pass the right pointer, and it never moves backward). Even though a single expansion or shrink may process multiple elements, the aggregate across all iterations is bounded by 2n.

💡

Invariant Template

For the opposite-direction two-pointer on a sorted array: "At the start of each iteration, a[left] + a[right] has not yet been tested, and no valid pair exists with indices outside the range [left, right]." For the variable-size sliding window: "The substring s[left..right] satisfies the constraint, and no larger valid window has its left boundary before left." Stating these invariants explicitly in comments above your while loop is a professional best practice that prevents subtle bugs.

SECTION 5

Pattern Classification & Sliding Window Diagram

Recognizing which pattern variant to apply is the key skill in competitive programming and technical interviews. The decision tree is surprisingly compact: if the problem involves a sorted sequence and a pair/triplet condition, reach for converging two-pointers; if it involves contiguous subarray/substring optimization, reach for a sliding window. The following diagram illustrates a variable-size sliding window finding the shortest subarray with a sum ≥ target.

This diagram shows a variable-size sliding window finding the shortest subarray with sum ≥ 15. The window expands rightward until the constraint is met, then shrinks from the left as long as the constraint holds. The minimum valid window length seen across all shrink phases is the answer.

Pattern Variant	When to Use	Typical Problems
Converging Two-Pointer	Sorted array, find pair/triplet satisfying a sum or difference condition	Two Sum II, 3Sum, Container With Most Water, Trapping Rain Water
Same-Direction Two-Pointer	In-place modification, partitioning, or slow/fast traversal of a sequence	Remove Duplicates, Move Zeroes, Linked List Cycle, Merge Sorted Arrays
Fixed-Size Window	Aggregate (sum, max, average) over every subarray/substring of length k	Max Sum Subarray of Size K, Sliding Window Maximum (with deque), String Hashing
Variable-Size Window	Find longest/shortest subarray or substring satisfying a dynamic constraint	Longest Substring Without Repeating Chars, Minimum Window Substring, Longest Repeating Character Replacement

Decision guide for selecting the appropriate pattern variant

SECTION 6

Worked Example — Longest Substring Without Repeating Characters

Consider the classic problem: given a string s, find the length of the longest substring without repeating characters. We will solve this using a variable-size sliding window in C++. The input is s = "abcabcbb", and the expected output is 3 (the substring "abc").

Longest Substring Without Repeating Characters

1
Step 1 — Identify the Pattern

We need the longest contiguous substring satisfying a constraint (no duplicate characters). This is a classic variable-size sliding window problem. We maintain a window [left, right] and a hash set (or frequency map) tracking characters currently in the window.
2
Step 2 — Set Up Data Structures

Declare int left = 0, maxLen = 0; and std::unordered_set<char> charSet;. The set tracks which characters are present in the current window. We iterate right from 0 to n−1.
3
Step 3 — Expand the Window

For each value of right, check if s[right] is already in charSet. If not, insert it and update maxLen = max(maxLen, right - left + 1). If yes, we must shrink.
4
Step 4 — Shrink the Window

While s[right] is in charSet, remove s[left] from the set and increment left. This continues until the duplicate is evicted, restoring the invariant that all characters in [left, right] are unique.
5
Step 5 — Trace on "abcabcbb"

right=0: add 'a', set={a}, maxLen=1. right=1: add 'b', set={a,b}, maxLen=2. right=2: add 'c', set={a,b,c}, maxLen=3. right=3: 'a' ∈ set → remove 'a', left=1, then add 'a', set={b,c,a}, maxLen=3. right=4: 'b' ∈ set → remove 'b', left=2, add 'b', set={c,a,b}, maxLen=3. Continuing similarly, we find no window longer than 3.

Answer: 3 — the longest substring without repeating characters is "abc" (or equivalently "bca" or "cab").
6
Step 6 — C++ Implementation

int lengthOfLongestSubstring(const std::string& s) { std::unordered_set<char> charSet; int left = 0, maxLen = 0; for (int right = 0; right < (int)s.size(); ++right) { while (charSet.count(s[right])) { charSet.erase(s[left]); ++left; } charSet.insert(s[right]); maxLen = std::max(maxLen, right - left + 1); } return maxLen; } Time complexity: O(n) amortized, since each character is inserted and erased at most once. Space complexity: O(min(n, |Σ|)) where |Σ| is the alphabet size.

SECTION 7

Strengths, Limitations & Comparison with Alternatives

The two-pointer and sliding window patterns are not silver bullets. Understanding when they apply—and when they do not—is as important as knowing how to implement them. The following comparison places these patterns alongside alternative approaches for common problem types.

Criterion	Two-Pointer / Sliding Window	Brute Force / Hash Map
Time Complexity	O(n) or O(n log n) if sorting is needed	O(n²) brute force; O(n) with hash map (but with higher constant factor)
Space Complexity	O(1) for two-pointer on sorted data; O(k) or O(\|Σ\|) for sliding window	O(n) for hash map; O(1) for brute force
Prerequisite	Sorted data (for converging pointers) or contiguous subarray structure (for windows)	No structural prerequisite; works on unsorted, non-contiguous data
Cache Performance	Excellent—sequential access pattern maximizes spatial locality	Hash map has poor locality due to random memory access; brute force varies
Code Complexity	Moderate—requires careful invariant management; off-by-one errors common	Brute force is trivially correct; hash map is straightforward but may have collision issues
Limitation	Cannot handle non-contiguous or unordered queries; fails when constraint is not monotonic	Hash map does not exploit order; brute force does not scale

Two-pointer/sliding window vs. alternative approaches

⚠

WHEN NOT TO USE THESE PATTERNS

These patterns require a monotonicity property: expanding or contracting the window (or advancing a pointer) must consistently change the aggregate in one direction. If a constraint can oscillate unpredictably—for example, if array elements include negative numbers and you seek a subarray sum ≥ target—the basic sliding window breaks down because adding an element might decrease the sum. In such cases, prefix sums with binary search or a monotone deque approach may be needed instead.

SECTION 8

Connection to Advanced Techniques

The two-pointer and sliding window patterns are gateway concepts that lead naturally to more sophisticated algorithmic techniques. Mastering them lays the groundwork for tackling problems that require additional data structure support within the window, multi-pass strategies, or more complex pointer movement schemes.

Introductory Pattern	Advanced Extension	Key Addition
Fixed-size sliding window (sum)	Sliding Window Maximum (Monotone Deque)	A deque maintains elements in decreasing order, enabling O(1) max queries per slide
Variable-size window (character set)	Minimum Window Substring (Frequency Maps)	Two frequency maps track required vs. window characters; a 'formed' counter avoids full map comparison
Converging two-pointer (pair sum)	3Sum / 4Sum (Nested Two-Pointer)	Fix one element and run two-pointer on the remainder; skip duplicates for O(n²) deduplication
Same-direction slow/fast pointer	Floyd's Cycle Detection & Linked List Midpoint	Fast pointer moves 2× speed; meeting point implies cycle; mathematical proof yields entry point
Sliding window with sum constraint	Prefix Sum + Binary Search (Negative Numbers)	Compute prefix sums, then for each index i, binary-search for the smallest j where prefix[j] − prefix[i] ≥ target

How introductory patterns connect to advanced techniques

As you progress, you will encounter problems that blend these patterns: a sliding window with a sorted container (e.g., std::multiset) to maintain order within the window, or two-pointer approaches combined with binary search for logarithmic inner queries. The foundational intuition you build here—that incremental state updates avoid redundant computation—is the unifying principle behind all of these extensions.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why the converging two-pointer technique for Two Sum on a sorted array is correct—that is, why can we guarantee that we never skip over a valid pair when we advance the left pointer on a small sum or the right pointer on a large sum?

Show answer

When the current sum is less than the target, advancing the left pointer is justified because the right pointer is already at the largest available value for the current left position: any smaller right index would produce an even smaller sum, so no valid pair involving the current left element and any right element at or beyond the current right pointer has been missed. Symmetrically, when the sum is too large, decrementing the right pointer is safe because any index left of the current left pointer has already been eliminated. This monotonicity argument—left movement can only increase the sum, right movement can only decrease it—ensures completeness in O(n) time.

Question 2: BASIC CALCULATION

Given the sorted array [2, 7, 11, 15] and target = 9, trace the converging two-pointer algorithm step by step. State the values of left, right, and the sum at each iteration.

Show answer

Initialize left=0, right=3. Iteration 1: a[0]+a[3] = 2+15 = 17 > 9, so right-- → right=2. Iteration 2: a[0]+a[2] = 2+11 = 13 > 9, so right-- → right=1. Iteration 3: a[0]+a[1] = 2+7 = 9 == target, return indices (0, 1). The algorithm found the answer in exactly 3 iterations, compared to the 6 pairs a brute-force approach would examine.

Question 3: INTERMEDIATE

Write a C++ function that uses a fixed-size sliding window to compute the maximum sum of any contiguous subarray of length k in an integer vector. Analyze the time and space complexity.

Show answer

The solution computes the sum of the first k elements, then slides the window:

int maxSumSubarray(const vector<int>& a, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; ++i) windowSum += a[i];
    int maxSum = windowSum;
    for (int i = k; i < (int)a.size(); ++i) {
        windowSum += a[i] - a[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

Time complexity is O(n) since each element is added once and subtracted once. Space complexity is O(1) as we only maintain two integer variables. The key insight is the recurrence: each new window sum is derived from the previous one by adding the incoming element and subtracting the outgoing element.

Question 4: APPLIED

A network monitoring system records packet sizes in a stream. You need to find the minimum number of consecutive packets whose total size is at least B bytes. Given packet sizes [100, 200, 50, 300, 150, 100, 250] and B = 500, find the answer using a variable-size sliding window. Show your work.

Show answer

Use a variable-size window: expand right until sum ≥ 500, then shrink left while sum ≥ 500, tracking the minimum length. Trace: expand to right=3 → sum=100+200+50+300=650 ≥ 500, len=4. Shrink: remove 100 → sum=550, len=3 (indices 1–3). Remove 200 → sum=350 < 500, stop. Expand to right=4 → sum=500, len=4 (indices 2–4). Shrink: remove 50 → sum=450 < 500. Expand to right=5 → sum=550, len=4 (indices 2–5). Shrink: remove 300 → sum=250 < 500 (skipping ahead). Expand to right=6 → sum=500, len=4 (indices 3–6). Shrink: remove 300 → sum=200 < 500. Minimum window seen: 3 (packets [200, 50, 300]). This runs in O(n) since both pointers traverse the array at most once.

Question 5: CRITICAL THINKING

Consider the problem of finding the longest subarray with sum ≤ S in an array that may contain negative numbers. Explain why the standard variable-size sliding window fails in this case, and propose an alternative O(n log n) approach. Outline the algorithm and justify its correctness.

Show answer

The standard sliding window assumes that shrinking from the left strictly decreases the window sum (monotonicity). With negative numbers, removing an element from the left could increase the sum, meaning we might skip valid longer windows. The fix uses prefix sums: compute prefix[i] = a[0] + ... + a[i−1]. The sum of subarray [i, j) equals prefix[j] − prefix[i]. We want the longest j − i such that prefix[j] − prefix[i] ≤ S. Build a prefix array, then maintain a monotone increasing sequence of prefix values (since if prefix[i₁] ≥ prefix[i₂] for i₁ < i₂, we would always prefer i₂). For each j, binary search this monotone sequence for the smallest prefix[i] ≥ prefix[j] − S. This yields O(n log n). Alternatively, use a balanced BST (e.g., std::set in C++) to store prefix values and query the lower_bound for each j. Both approaches correctly handle negative numbers by abandoning the monotonicity assumption that the basic sliding window requires.

SUMMARY

Summary

The two-pointer technique and sliding window pattern are foundational strategies for transforming O(n²) brute-force scans into O(n) linear traversals. The converging two-pointer variant places pointers at opposite ends of a sorted array and leverages monotonicity to prune the search space. The same-direction two-pointer moves both pointers forward, enabling in-place modifications and cycle detection. The fixed-size sliding window computes aggregates over every k-length subarray by adding one element and removing another per step. The variable-size sliding window dynamically expands and contracts to find optimal subarrays or substrings under a constraint.

The correctness of every variant rests on a carefully stated loop invariant and the monotonicity property of the constraint: advancing a pointer must change the aggregate in a predictable direction. When this property holds, amortized analysis shows that each element is processed O(1) times on average. When it does not—such as with negative numbers in sum problems—more sophisticated approaches like prefix sums with binary search or monotone deques become necessary, but the underlying incremental-update intuition remains the same.