Why Patterns Matter
Coding interviews don't test whether you've memorized 500 LeetCode solutions. They test whether you can recognize which pattern applies and adapt it to a new problem. Four pattern families cover the vast majority of array, string, and linked list problems you'll encounter.
- Two pointers (opposite direction): Start from both ends, shrink inward. Used for sorted arrays, palindromes, and pair-finding.
- Two pointers (same direction / fast & slow): One pointer leads, the other trails. Used for cycle detection, removing duplicates, and linked list problems.
- Sliding window (fixed size): A window of constant width slides across the array. Used for max/min/average of subarrays of size K.
- Sliding window (variable size): The window expands and contracts based on a condition. Used for smallest/largest subarray with a given property.
Two Pointers — Opposite Direction
Place one pointer at the start and one at the end. Move them toward each other based on a condition. This eliminates the need for nested loops, reducing O(n²) to O(n).
Two Pointers Moving Inward
When to use: The array is sorted and you're searching for a pair, triplet, or condition that involves elements from both ends. Classic examples: two-sum on sorted array, container with most water, valid palindrome, and 3Sum.
Two Pointers — Same Direction (Fast & Slow)
Both pointers start at the same position and move in the same direction, but at different speeds. The "fast" pointer explores ahead while the "slow" pointer marks a position of interest.
Fast & Slow Pointers on a Linked List
When to use: Cycle detection in linked lists (Floyd's algorithm), finding the middle of a linked list, removing the N-th node from end, and removing duplicates from sorted arrays.
Problem: Container With Most Water
Given n non-negative integers representing heights, find two lines that together with the x-axis form a container holding the most water. This is a classic two pointers (opposite direction) problem.
Approach: Start with the widest container (left = 0, right = n-1). The area = min(height[left], height[right]) * (right - left). Move the pointer pointing to the shorter line inward, because moving the taller one can only decrease or maintain the area.
Problem: 3Sum
Given an array of integers, find all unique triplets [a, b, c] such that a + b + c = 0. This combines sorting + two pointers (opposite direction).
Approach: Sort the array. Fix one element, then use two pointers on the remaining subarray to find pairs that sum to the target. Skip duplicates at every level to avoid repeated triplets.
Sliding Window — Fixed Size
A window of exactly K elements slides across the array one position at a time. Instead of recalculating the sum/property from scratch for each position (O(n*K)), you add the new element and remove the old one (O(1) per step).
Fixed-Size Sliding Window (K = 3)
Template:
- Compute the sum/property of the first window (indices 0 to K-1).
- Slide: add
arr[i], removearr[i - K]. - Track the best (max, min, etc.) as you go.
Sliding Window — Variable Size
The window expands by moving the right pointer and shrinks by moving the left pointer when a condition is violated. This is used for "smallest/longest subarray with property X" problems.
Variable-Size Window: Expand & Shrink
Template:
- Initialize
left = 0. Moverightforward one step at a time. - Expand: add
s[right]to the window's state (hash map, count, sum). - Shrink: while the window satisfies the condition, try to minimize it by moving
leftforward and updating the best answer. - Return the best answer.
Problem: Maximum Sum Subarray of Size K
Given an array of integers and a number K, find the maximum sum of any contiguous subarray of size K. This is the simplest fixed-size sliding window problem.
Problem: Minimum Window Substring
Given strings s and t, find the smallest substring of s that contains all characters of t (including duplicates). This is a classic variable-size sliding window problem.
Approach: Expand right to include characters. When all characters of t are covered, shrink left to find the minimum window. Use a hash map to track character counts.
Fast & Slow Pointers — Floyd's Cycle Detection
Floyd's algorithm uses two pointers moving at different speeds. If there's a cycle, the fast pointer will eventually "lap" the slow pointer and they'll meet inside the cycle. This detects cycles in O(n) time with O(1) space — no hash set needed.
- Phase 1 (Detect): Slow moves +1, fast moves +2. If they meet, a cycle exists.
- Phase 2 (Locate start): Reset one pointer to head. Move both +1. Where they meet is the cycle start.
- Why Phase 2 works: If the distance from head to cycle start is
a, and the meeting point isbsteps into the cycle, then the math guarantees both pointers meet at the cycle start when one starts from head.
Problem: Linked List Cycle Start
Given a linked list, return the node where the cycle begins. If there is no cycle, return None.
Pattern Decision Tree
Use this flowchart when you encounter a new problem. Ask yourself these questions in order to identify which pattern to apply:
Which Searching Pattern Should I Use?
| Pattern | When to Use | Time | Classic Problems |
|---|---|---|---|
| Two Pointers (Opposite) | Sorted array, pairs, triplets | O(n) | Container Water, 3Sum, Two Sum II |
| Two Pointers (Same) | Remove duplicates, partition | O(n) | Remove Duplicates, Move Zeroes |
| Fixed Sliding Window | Subarray of exact size K | O(n) | Max Sum K, Max Avg Subarray |
| Variable Sliding Window | Smallest/longest with condition | O(n) | Min Window Substring, Longest No Repeat |
| Fast & Slow Pointers | Cycle detection, middle node | O(n) | Cycle Start, Happy Number, Middle Node |
Try It Yourself
Find Maximum Sum Subarray of Size K
Implement the sliding window technique to find the maximum sum of any contiguous subarray of size K. The starter code has the function signature — fill in the logic using a fixed-size sliding window.
Challenge
Given a string s, find the length of the longest substring without repeating characters. For example, "abcabcbb" returns 3 (the substring "abc").
Pattern: Variable-size sliding window
max(best, right - left + 1) at each step. Time: O(n), space: O(min(n, alphabet size)).Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. For example, [0,1,0,2,1,0,1,3,2,1,2,1] returns 6.
Pattern: Two pointers (opposite direction)
left_max and right_max. If height[left] < height[right], the water at left is determined by left_max: add left_max - height[left] if positive, then move left. Otherwise, process right similarly. Time: O(n), space: O(1).Quiz
Common Mistakes
- Forgetting to skip duplicates in 3Sum. Without duplicate-skipping,
[-1, -1, 0, 1]produces[[-1, 0, 1], [-1, 0, 1]]. Always skip duplicates at every pointer level after sorting. - Thinking the nested while loop in sliding window is O(n²). Each element is added once and removed at most once. The inner loop's total work across all iterations is O(n), making the overall complexity O(n).
- Using a hash set for cycle detection when O(1) space is required. Floyd's algorithm detects cycles with two pointers and O(1) space. A hash set works but uses O(n) space — interviewers often want the constant-space solution.
- Off-by-one in window boundaries. In fixed sliding window, the first window covers indices
[0, K-1]. The slide starts at indexKand removes indexi - K. Drawing out a small example helps catch boundary errors. - Forgetting to handle the "no valid window" case. In minimum window substring, if no valid window exists, return an empty string. Initialize your best to infinity and check before returning.
Key Takeaways
- Two pointers (opposite direction) turns O(n²) pair-finding into O(n) by shrinking from both ends. Requires a sorted array. Used in container with most water, 3Sum, and two-sum variants.
- Fixed sliding window processes subarrays of size K in O(n) by incrementally adding and removing one element per step. Used for max sum, max average, and string permutation checks.
- Variable sliding window expands right and shrinks left based on a condition, finding optimal subarrays in O(n). Used for minimum window substring, longest substring without repeating characters.
- Fast & slow pointers (Floyd's) detect cycles in O(n) time with O(1) space by moving at different speeds. Phase 2 finds the cycle start by resetting one pointer to head.
- Pattern recognition is the meta-skill. Instead of memorizing solutions, learn to recognize: sorted pairs → two pointers, subarray of size K → fixed window, shortest with property X → variable window, cycle → Floyd's.
You've mastered searching patterns.
Now find the career opportunity you deserve.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →