Chapter 3: Two Pointers & Sliding Window
Master the two pointer technique for scanning sequences from both ends or in tandem, then learn sliding window patterns that maintain a moving subarray to solve range-based problems in linear time. These patterns eliminate nested loops and are among the most frequently tested in interviews.
Chapter Overview
Two pointers and sliding window are arguably the highest-value patterns in all of DSA interviewing. They transform problems that seem to require O(n^2) brute force into elegant O(n) solutions by maintaining state as pointers sweep through the data.
Two pointers come in two flavors. Same-direction pointers (often called "slow and fast") walk through the array together, with the fast pointer exploring ahead while the slow pointer marks a boundary. Opposite-direction pointers start at both ends and move inward, exploiting sorted order or symmetry to skip unnecessary comparisons.
Sliding window extends the two-pointer idea to subarrays and substrings. A fixed-size window slides across the array, updating its aggregate in O(1) per step. A variable-size window expands to include new elements and shrinks from the left when a constraint is violated, solving "longest/shortest subarray with property X" problems efficiently.
Finally, we cover two closely related techniques: prefix sums, which precompute cumulative totals so any range sum can be answered in O(1), and Floyd's cycle detection, which uses fast and slow pointers on linked structures to detect loops in O(1) space.
This chapter covers:
- Same & opposite direction pointers: Core two-pointer strategies
- Classic two-pointer problems: Remove duplicates, two sum sorted, valid palindrome
- Fixed-size sliding window: Maximum sum subarray of size k
- Variable-size sliding window: Longest and shortest windows with constraints
- Prefix sums: O(1) range queries after O(n) preprocessing
- Cycle detection: Floyd's tortoise and hare algorithm
Chapter Roadmap
Click any topic to jump in
Two Pointers
Two indices walking an array together — the building block for in-place transforms, pair search, and sliding windows.
Same-direction pointers for in-place rewriting, opposite-direction for pair search.
In-Place Rewriting
Same-direction pointers (read/write) compact arrays in $O(n)$ time and $O(1)$ extra memory.
Two Sum / Three Sum
Opposite-direction pointers find target pairs on sorted arrays in linear time — the basis of $k$-sum reductions.
Palindrome Checks
Opposite-direction pointers compare mirrored positions — extensions handle filtering and tolerated mismatches.
Sliding windows generalise two pointers to maintain state over a contiguous range.
Fixed Window
A window of exactly $k$ elements — amortised $O(1)$ per step using incremental updates.
Variable Window
Expand-then-shrink windows — each index is visited at most twice, keeping the total $O(n)$.
Prefix sums answer range queries; tortoise & hare uses two pointers on linked structures.
Prefix Sums
Cumulative sums turn range-sum queries into two array reads — combine with hash maps for subarray-sum problems.
Floyd's Tortoise & Hare
Two pointers moving at different speeds detect cycles in $O(n)$ time and $O(1)$ space.
The two pointer technique uses two index variables to scan through an array or string. Instead of checking every pair with nested loops (O(n^2)), pointers move strategically so each element is visited a constant number of times, yielding O(n) solutions.
Same-direction pointers both start at one end. A fast pointer explores ahead while a slow pointer trails behind, maintaining an invariant such as "everything before slow satisfies a condition." Opposite-direction pointers start at both ends and walk inward, commonly used on sorted arrays where you can decide which end to advance based on the current sum or comparison.
In this topic
Same-Direction (Fast & Slow) Pointers
Both pointers start at the beginning. The fast pointer advances every iteration, while the slow pointer advances only when a condition is met. This partitions the array into two regions: elements before the slow pointer that satisfy the condition, and elements between slow and fast that have been processed but filtered out. This pattern is used for in-place removal, deduplication, and partitioning.
Two indices (fast, read) and (slow, write) both advance from . The invariant is that already holds the finalised output. Because each pointer moves only forward and at most times, the total work is time and extra space — strictly better than any solution that allocates a new array.
Given an array [0, 1, 0, 3, 12], move all zeros to the end while maintaining the relative order of non-zero elements. Do this in-place.
Opposite-Direction Pointers
One pointer starts at the beginning, the other at the end. They move toward each other based on a comparison or condition. This is ideal for sorted arrays (where the sum of endpoints guides which pointer to move), palindrome checking (comparing characters from both ends), and container problems (where width decreases as pointers converge). The loop runs while left < right, visiting each element at most once for O(n) time.
Two indices (from the left) and (from the right) close in on each other. At each step one of them moves inward, so the combined distance decreases by at least per iteration. Starting from , the loop runs at most times — . The invariant depends on the problem (e.g., 'the answer, if any, involves some and ').
Given a sorted array [-4, -1, 0, 3, 10], return a new array of each element squared, sorted in non-decreasing order.