Recap — Two Pointers and Sliding Window Patterns

# Two Pointers and Sliding Window Patterns Both patterns convert a naive O(N²) brute force into O(N). They appear in 30%+ of array/string interview problems. ## Two Pointers Use when: - Array is sorted (or sortable). - Looking for a pair that satisfies some property. - You can move pointers based on comparison. ### Pattern 1: Opposite ends (converge) ```python def two_sum_sorted(arr, target): left, right = 0, len(arr) - 1 while left < right: s = arr[left] + arr[right] if s == target: return [left, right] elif s < target: left += 1 # need bigger sum else: right -= 1 # need smaller sum return [] ``` Total work: each pointer moves at most N times → O(N). Other examples: - Reverse a string in-place - Check palindrome - 3Sum (fix one element, two-pointer the rest) - Container with most water ### Pattern 2: Same direction (fast/slow) ```python def remove_duplicates(arr): if not arr: return 0 write = 0 for read in range(1, len(arr)): if arr[read] != arr[write]: write += 1 arr[write] = arr[read] return write + 1 ``` Fast pointer reads; slow pointer writes. Common for in-place modifications. Other examples: - Linked list cycle detection (Floyd's algorithm) - Find middle of linked list - Move zeros to end ## Sliding Window Use when: - Looking for a contiguous subarray/substring with some property. - "Maximum/minimum length", "longest", "smallest", "shortest" of substring matching a constraint. ### Pattern: Variable-size window ```python def longest_substring_without_repeat(s): seen = {} left = 0 best = 0 for right in range(len(s)): if s[right] in seen and seen[s[right]] >= left: left = seen[s[right]] + 1 seen[s[right]] = right best = max(best, right - left + 1) return best ``` The window [left, right] grows from the right; shrinks from the left when the constraint is violated. Total work: each character enters the window once and exits at most once → O(N). ### Pattern: Fixed-size window ```python def max_sum_subarray_size_k(arr, k): window_sum = sum(arr[:k]) best = window_sum for i in range(k, len(arr)): window_sum += arr[i] - arr[i - k] # slide: add new, drop old best = max(best, window_sum) return best ``` Window size stays at k; slide by one. ### Common sliding-window problems - Longest substring without repeating characters - Longest substring with at most K distinct characters - Minimum window substring (contains all chars of T) - Maximum sum subarray of size K - Permutation/anagram in string ## How to recognize each pattern in an interview **Two pointers** clues: - "Sorted array" or "you can sort it" - "Find a pair/triplet" - "In-place modification" - "Palindrome" - "Linked list cycle/middle" **Sliding window** clues: - "Contiguous subarray/substring" - "Longest" / "shortest" / "maximum sum" - "At most K" / "exactly K" / "no repeats" - "Window size K" ## The decision tree ``` Problem about arrays/strings? ├── Need to find subarray/substring contiguous? │ ├── Yes → sliding window │ └── No → continue ├── Array is sorted (or you can sort)? │ ├── Yes → two pointers (opposite ends usually) │ └── No → consider hashmap or sort first └── Need in-place modification? └── Two pointers (same direction) ``` ## Common mistakes 1. **Forgetting to shrink the window.** Sliding window must shrink when constraint is violated; otherwise O(N²). 2. **Off-by-one on window bounds.** `right - left + 1` for inclusive size; check the boundary conditions carefully. 3. **Sorting when you didn't need to.** If you sort, you lose original indices. For "return indices", consider hashmap instead. 4. **Two pointers on unsorted data.** Doesn't work; either sort first or use a different pattern. ## Takeaway Two pointers and sliding window each convert O(N²) brute force into O(N). Recognize by problem signals: "sorted + pair" → two pointers; "contiguous + maximum/minimum" → sliding window. Practice the canonical 5-6 problems for each; everything else is a variant.