tags: - cocubes - coding - dsa
Coding Pattern Catalog
1. Linear scan
Use when you need sum, min, max, count, existence or first position.
Time O(n), extra space O(1).
Examples: largest array element, count evens, sum of cards.
2. Frequency map
Use a hash map/dictionary for counts or matching values.
Time O(n) average, space O(n).
Examples: first non-repeating character, duplicate detection, two-sum, anagram check.
3. Sorting
Sort when order makes the problem simple.
Time usually O(n log n).
Examples: remove duplicates, merge intervals, two pointers on a sorted array, closest pair.
4. Two pointers
Usually one pointer at each end, or a slow/fast pair.
Examples:
- palindrome string;
- pair sum in sorted array;
- remove duplicates in sorted array;
- cycle detection in linked list using slow/fast pointers.
5. Sliding window
Maintain a contiguous range with left and right pointers.
Examples: maximum sum subarray of size k, longest substring with a constraint.
6. Prefix sum
Precompute cumulative sums so a range sum is O(1).
prefix[i] = sum of elements before i, depending on indexing convention.
Examples: range-sum queries, count subarrays with target sum plus frequency map.
7. Stack
Examples: balanced brackets, next greater element, expression evaluation.
For balanced brackets: push opens; on close, top must be matching open; stack must be empty at end.
8. Binary search
Use for sorted data or monotonic answer space.
Invariant method:
- maintain left/right valid bounds;
- calculate middle safely;
- decide which half cannot contain answer;
- update one bound, guaranteeing progress.
9. Recursion/backtracking
Use only if input limits are small or the problem naturally branches. Always write base case first.
10. Matrix/grid traversal
Use direction arrays for four neighbours. Check boundaries before accessing. BFS handles shortest unweighted grid paths; DFS handles exploration/components.
Pattern selection guide
| Phrase in problem | First pattern to consider |
|---|---|
| count/frequency/duplicate | hash map |
| contiguous subarray/substring | sliding window or prefix sum |
| sorted array/pair | two pointers or binary search |
| matching brackets | stack |
| minimum/maximum repeatedly | heap |
| shortest steps in unweighted grid | BFS |
| simple numeric digits/power | modulo/cycle |
[[05_Coding/Coding_Problems|Practice problems]] · [[05_Coding/Coding_Playbook|Playbook]]