Two pointers and sliding window are among the most powerful techniques for solving array and string problems efficiently. They reduce brute-force O(N^2) solutions to O(N) by maintaining a window or pair of pointers that move through the data in a single pass. This guide covers the core patterns, when to apply each, and the most common interview problems — giving you a systematic approach to these questions.
Two Pointers: Opposite Direction
Pattern: two pointers start at opposite ends of a sorted array and move toward each other. Use when: the array is sorted and you need to find pairs or check a condition involving elements from both ends. Classic problem: Two Sum on a sorted array. left = 0, right = N-1. If array[left] + array[right] == target, found. If sum target, move right left (need a smaller number). Time: O(N). Other applications: Container With Most Water (maximize area between two lines — move the shorter line inward), Valid Palindrome (compare characters from both ends), 3Sum (fix one element, two-pointer on the rest). Key insight: the sorted order guarantees that moving a pointer in one direction consistently increases or decreases the value, enabling systematic elimination of candidates without checking all pairs.
Two Pointers: Same Direction (Fast-Slow)
Pattern: two pointers move in the same direction at different speeds. Use when: you need to detect cycles, find the middle of a linked list, or partition an array in-place. Linked list cycle detection (Floyd algorithm): slow pointer moves 1 step at a time, fast pointer moves 2 steps. If there is a cycle, they will meet. If fast reaches null, no cycle. To find the cycle start: after they meet, move one pointer to the head. Advance both at speed 1. They meet at the cycle start. Find the middle of a linked list: slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle. Remove duplicates from sorted array: slow marks the position for the next unique element. fast scans ahead. When fast finds a new value, copy it to slow+1 and advance slow. Move zeroes: similar pattern — slow marks the position for the next non-zero, fast scans for non-zeroes. Key insight: the speed difference between pointers creates a useful mathematical relationship (for cycle detection) or allows one pointer to “scout ahead” while the other marks a boundary.
Fixed-Size Sliding Window
Pattern: maintain a window of exactly K elements that slides one position at a time. Use when: you need to compute a function over every contiguous subarray of size K. Maximum sum subarray of size K: maintain a running sum. Add the element entering the window (right), subtract the element leaving the window (left). Track the maximum sum. Time: O(N). Maximum of sliding window (hard): maintain a monotonic decreasing deque. Elements in the deque are potential maximums. When sliding the window: remove elements from the front that are outside the window. Remove elements from the back that are smaller than the new element (they can never be the maximum while the new element is in the window). The front of the deque is always the current maximum. Time: O(N) because each element is added and removed from the deque at most once. String permutation check: given strings s1 and s2, check if any permutation of s1 is a substring of s2. Maintain a frequency count window of size len(s1) sliding over s2. Compare frequency counts at each position. Time: O(N) with a fixed-size frequency array.
Variable-Size Sliding Window
Pattern: the window expands (right pointer moves right) until a condition is met, then contracts (left pointer moves right) to find the optimal size. Use when: you need to find the smallest or longest subarray/substring satisfying a condition. Minimum size subarray sum: find the smallest contiguous subarray with sum >= target. Expand right to increase the sum. When sum >= target, try to shrink from the left while maintaining the condition. Track the minimum window size. Time: O(N). Longest substring without repeating characters: expand right, adding characters to a set. If a duplicate is found, shrink from the left until the duplicate is removed. Track the maximum window size. Time: O(N). Minimum window substring: find the smallest substring of s that contains all characters of t. Use a frequency map. Expand right to include characters. When all of t characters are covered, shrink from left to minimize. Track the minimum window. Time: O(N). Template: initialize left = 0, result = infinity (or 0). For right in range(N): add element at right to the window state. While window condition is satisfied (or violated, depending on the problem): update result, remove element at left from window state, left++. This template handles most variable-size sliding window problems.
Pattern Recognition Guide
How to identify which pattern to use: (1) “Find a pair in a sorted array” -> two pointers, opposite direction. (2) “Detect cycle in linked list” or “find middle” -> fast-slow pointers. (3) “Compute something over every subarray of size K” -> fixed-size sliding window. (4) “Find the smallest/longest subarray satisfying a condition” -> variable-size sliding window. (5) “Partition array in-place” or “remove elements” -> same-direction two pointers. (6) “Check if one string is a permutation/anagram of another” -> sliding window with frequency count. Common pitfalls: (1) Forgetting to handle the window state correctly when shrinking (removing the left element from the frequency map or sum). (2) Off-by-one errors in window boundaries. (3) Not recognizing that the problem can be solved with a sliding window (if the problem asks about contiguous subarrays, consider sliding window). Practice: solve 3-5 problems per pattern. Two Sum II, Container With Most Water, 3Sum (opposite pointers). Linked list cycle, remove duplicates (fast-slow). Max sum subarray K, sliding window maximum (fixed window). Min window substring, longest without repeating (variable window).