DSA: Advanced Problem-Solving Patterns
Recognize and apply the universal patterns behind sliding window, two pointers, monotonic stack, and more.
Sliding Window (Fixed and Variable Size)
Sliding window avoids recomputing from scratch by maintaining a running result as the window moves: add the new right element, remove the leftmost. Fixed-size windows have constant k; variable-size windows expand right and shrink left based on a constraint.
Sliding Window
Fixed: O(n) by adding right and removing left each step. Variable: expand right freely, shrink left when constraint violated.
- Fixed size k: window sum update = sum + arr[r] - arr[r-k]
- Variable size: two pointers l and r; shrink l while window is invalid
- Common constraints: max sum, distinct characters, at most k distinct, no repeats
- Time: O(n): each element enters and exits the window at most once
Longest Substring Without Repeating Characters
C++Variable window: shrink left past the previous occurrence of the duplicate.
Two Pointers Technique
Two pointers start at opposite ends (or both at the start) and move inward or forward based on a comparison. Works on sorted arrays and eliminates the need for nested loops.
Two Pointers
Opposite ends: move left right or right left based on sum vs target. Same direction: fast advances, slow lags.
- Two Sum (sorted): l=0, r=n-1; if sum < target move l right; if sum > target move r left
- Remove duplicates: slow pointer marks write position; fast scans forward
- Container with most water: move the pointer with the shorter height
- Time: O(n): each pointer traverses at most n positions
Two Pointers
C++Two Sum and remove duplicates: O(n) with opposite-end and same-direction pointers.
Fast and Slow Pointers
Fast moves 2 steps per iteration; slow moves 1. If a cycle exists they will meet. Used for cycle detection, finding the cycle start, and finding the middle of a linked list.
Fast and Slow Pointers (Floyd's Algorithm)
Meeting point proves a cycle. Reset one pointer to head; advance both one step at a time to find cycle start.
- Cycle detection: fast and slow meet inside the cycle
- Cycle start: reset slow to head; advance both one step at a time; they meet at cycle start
- Middle of list: when fast reaches end, slow is at the middle
- Happy number: same pattern, fast computes two digit-sum steps, slow one
Cycle Detection and Start (Floyd's Algorithm)
C++Meet inside cycle, then reset one pointer to head; both advance one step to find start.
Cyclic Sort Pattern
When an array contains numbers in range [1, n], each number belongs at index value-1. Swap each element to its correct position in O(n) without extra space.
Cyclic Sort
Place arr[i] at index arr[i]-1. After sorting, any index where arr[i] != i+1 reveals a missing or duplicate.
- While arr[i] != i+1: swap arr[i] with arr[arr[i]-1]
- After sort: scan for arr[i] != i+1 to find missing numbers
- Time: O(n), Space: O(1), each element swapped at most once
- Works for: find missing number, find duplicate, find all missing numbers
Cyclic Sort: Find Missing Number
C++Place each element at its correct index; scan for the misplaced slot.
Top K Elements Pattern
Maintain a min-heap of size k. For each new element, if it is larger than the heap root, replace the root. After processing all elements, the heap contains the k largest.
Top K Elements
Min-heap of size k: root = smallest of the k largest seen so far. Replace root when a larger element arrives.
- Min-heap of size k: O(n log k) total, much better than O(n log n) sort
- Top K frequent: use frequency map, then min-heap on frequency
- Kth largest element: heap root after processing all n elements
- Alternative: QuickSelect gives O(n) average for kth element
Top K Frequent Elements
C++Frequency map + min-heap of size k: O(n log k) instead of O(n log n).
Modified Binary Search
Binary search applies beyond sorted arrays. In a rotated sorted array, one half is always sorted. Identify the sorted half, check if the target lies within it, and discard the other half.
Modified Binary Search
Rotated array: at least one half is sorted. Check mid against lo; determine which half is sorted, then check target range.
- If arr[lo] <= arr[mid]: left half is sorted
- If target in [arr[lo], arr[mid]): search left half, else right
- Otherwise right half is sorted; similar check for right range
- Time: O(log n): same as standard binary search
- Also applies to: find minimum in rotated array, search in nearly sorted array
Search in Rotated Sorted Array
C++One half is always sorted; check which, then narrow search to the correct half.
Monotonic Stack
A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element breaks the order, pop elements until the order is restored, those pops reveal the answer.
Monotonic Stack
Decreasing stack for Next Greater Element: the element that causes a pop is the next greater for all popped elements.
- Push indices, not values, needed to compute distances or spans
- Next Greater Element: maintain decreasing stack; on larger element, pop and record answer
- Daily Temperatures: same pattern, pop when warmer day found
- Largest Rectangle in Histogram: monotonic increasing stack
- Time: O(n): each element pushed and popped at most once
Next Greater Element
C++Decreasing monotonic stack: popping on larger element records the next greater.
Prefix Sum and Subarray Sum Equals K
Prefix sum enables O(1) range sum queries after O(n) preprocessing. For counting subarrays with sum equal to k, store prefix sum frequencies in a hash map.
Prefix Sum
prefix[i] = sum of arr[0..i-1]. Sum of arr[l..r] = prefix[r+1] - prefix[l]. O(1) per query.
- Build: prefix[0] = 0; prefix[i] = prefix[i-1] + arr[i-1]
- Range sum [l, r]: prefix[r+1] - prefix[l]
- Subarray sum = k: count prefix sums equal to (currentSum - k) seen so far
- Difference array: for range update [l,r] add v, use prefix sum to reconstruct
- 2D prefix sum: rectangle sum queries in O(1) after O(n²) build
Subarray Sum Equals K
C++Prefix sum + hash map: count previous sums equal to (currentSum - k).
Pattern Recognition Guide
Match the problem description to the right pattern before coding.
| Pattern | Trigger phrase | Time |
|---|---|---|
| Sliding Window (fixed) | "subarray/substring of size k" | O(n) |
| Sliding Window (variable) | "longest/shortest subarray satisfying..." | O(n) |
| Two Pointers | "sorted array, pair with sum/target" | O(n) |
| Fast and Slow Pointers | "cycle in linked list / middle node" | O(n) |
| Cyclic Sort | "array of 1..n, find missing/duplicate" | O(n) |
| Top K Elements | "k largest/smallest/most frequent" | O(n log k) |
| Modified Binary Search | "sorted but rotated / nearly sorted" | O(log n) |
| Monotonic Stack | "next greater/smaller element, span" | O(n) |
| Prefix Sum | "range sum query / subarray sum = k" | O(1) query |
| Bitmask DP | "subsets, assignment, visit all nodes" | O(2^n * n) |
Knowledge Check
1. Fixed-size sliding window of size k maintains the window by:
2. Variable-size sliding window shrinks the left pointer when:
3. Fast and slow pointer cycle detection (Floyd's algorithm): a cycle exists if:
4. Top K elements pattern uses a min-heap of size k because:
5. Modified Binary Search on a rotated sorted array works because:
6. Prefix sum array enables subarray sum queries in:
7. Monotonic stack solves Next Greater Element because:
8. Cyclic sort places element with value v at index: