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).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When do you use two pointers versus sliding window?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two pointers (opposite direction): use on sorted arrays when finding pairs. Both pointers start at ends and move inward. Problems: Two Sum (sorted), Container With Most Water, Valid Palindrome, 3Sum. Two pointers (same direction / fast-slow): use for cycle detection, finding middle of linked list, or in-place array modification. Problems: linked list cycle, remove duplicates from sorted array, move zeroes. Fixed-size sliding window: use when computing a function over every contiguous subarray of exactly K elements. Problems: maximum sum subarray of size K, sliding window maximum, string permutation check. Variable-size sliding window: use when finding the smallest or longest subarray satisfying a condition. Problems: minimum size subarray sum, longest substring without repeating characters, minimum window substring. Key signal: if the problem involves contiguous subarrays or substrings and asks for optimal length, try sliding window. If it involves pairs in a sorted array, try two pointers.”}},{“@type”:”Question”,”name”:”How does the variable-size sliding window template work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Template for most variable-size sliding window problems: initialize left = 0, best_result. For right in range(N): add the element at right to the window state (frequency map, running sum, etc.). While the window condition is satisfied (or violated): update best_result if current window is better, remove the element at left from window state, left++. Return best_result. Example — longest substring without repeating characters: window state is a set of characters. Expand right, add character to set. While a duplicate exists (character already in set), remove left character from set, left++. Track maximum (right – left + 1). Time: O(N) because each element is added and removed at most once. The key insight: the left pointer only moves right, never backward. Both pointers together visit at most 2N positions total, giving O(N) time regardless of how many times the inner while loop executes.”}},{“@type”:”Question”,”name”:”How does Floyd cycle detection algorithm work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Floyd algorithm uses two pointers moving at different speeds to detect cycles in a linked list. Slow pointer moves 1 step per iteration, fast pointer moves 2 steps. If there is no cycle, fast reaches null. If there is a cycle, fast and slow will eventually meet inside the cycle. Proof: once both are in the cycle, the fast pointer closes the gap by 1 node per iteration (relative speed = 1), so they must meet. Finding the cycle start: after slow and fast meet, move one pointer back to the head. Advance both at speed 1. They meet at the cycle start. Mathematical proof: let d = distance from head to cycle start, and k = distance from cycle start to meeting point. At meeting: slow traveled d + k, fast traveled d + k + n*cycle_length. Since fast travels 2x slow: 2(d+k) = d + k + n*cycle_length, so d = n*cycle_length – k. Moving one pointer d steps from the head and the other d steps from the meeting point (which is k steps into the cycle) both arrive at the cycle start.”}},{“@type”:”Question”,”name”:”What are the most important problems to practice for two pointers and sliding window?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Essential practice problems by pattern: Opposite-direction two pointers: Two Sum II (sorted array), Container With Most Water, 3Sum, Trapping Rain Water. Fast-slow pointers: Linked List Cycle, Linked List Cycle II (find start), Middle of Linked List, Remove Duplicates from Sorted Array, Move Zeroes. Fixed-size sliding window: Maximum Average Subarray I, Sliding Window Maximum (hard, uses monotonic deque), Find All Anagrams in a String. Variable-size sliding window: Minimum Size Subarray Sum, Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Repeating Character Replacement. Solve 3-5 per pattern until recognition is automatic. The variable-size sliding window template alone solves dozens of LeetCode problems. Master the template, then adapt it to each problem specific condition and state tracking.”}}]}