Search / Lookup
- Fast lookup / membership test
Strategy: HashSet / HashMap
Note: O(1) average-case lookup
Explanation: Hash tables allow constant-time key access; use set.contains(x) or map[x].
- Frequency count
Strategy: HashMap
Note: Count items or characters
Explanation: Map each item to its count: map[char]++ in loops.
- Finding duplicates
Strategy: HashSet
Note: Add each item, check if exists
Explanation: If already in set, it's a duplicate.
- Prefix/suffix search
Strategy: Trie
Note: For string problems with many prefixes
Explanation: Tree structure where each node is a char; enables fast prefix queries like autocomplete.
Sorting / Ordering
- Kth largest/smallest
Strategy: Heap (PriorityQueue)
Note: Efficient top-K access
Explanation: Use min-heap for kth largest in stream; max-heap for kth smallest.
- Custom sort
Strategy: Comparator / Sort
Note: Sort by custom logic
Explanation: Define how to compare items, e.g. by frequency, length, etc.
- Real-time median
Strategy: Two Heaps
Note: MinHeap and MaxHeap
Explanation: Max-heap for left half, min-heap for right half; maintain balance.
Graphs / Traversal
- Shortest path (unweighted)
Strategy: BFS
Note: Explore level-by-level
Explanation: Use a queue to explore neighbors first (shortest in steps).
- Shortest path (weighted)
Strategy: Dijkstra / A*
Note: Use priority queue
Explanation: Greedy: explore cheapest path first with cost tracking.
- Traverse all options
Strategy: DFS / BFS
Note: Based on need
Explanation: DFS for deep path search, BFS for shortest path or layer-wise search.
- Detect cycles / components
Strategy: Union-Find (DSU)
Note: Dynamic connectivity
Explanation: Merge/find root of components; useful in Kruskals or cycle detection.
- Topological sort
Strategy: DFS or Kahns Algo
Note: For DAGs
Explanation: Order of tasks with dependencies. Kahn uses indegree; DFS uses post-order.
Dynamic Programming (DP)
- Optimal substructure
Strategy: DP (memo/table)
Note: Store overlapping results
Explanation: Reuse results of subproblems to avoid recomputation.
- Ways to reach target
Strategy: DP (1D/2D)
Note: Count possibilities
Explanation: Ex: Number of ways to climb stairs = dp[i] = dp[i-1] + dp[i-2].
- Max/min cost, length, etc.
Strategy: Bottom-up DP
Note: Fill table iteratively
Explanation: Tabulation instead of recursion. Often faster and avoids stack overflow.
Sliding Window / Two Pointers
- Subarray with property
Strategy: Sliding Window
Note: Expand/shrink window
Explanation: Keep track of a range of indices that meet a condition (like sum, chars).
- Pairs/triplets with sum
Strategy: Two Pointers
Note: Use sorted array
Explanation: Start from both ends, move inward based on sum comparison.
- Min/max in window
Strategy: Deque / Monotonic Queue
Note: Efficient in O(n)
Explanation: Keep deque of indices in increasing/decreasing order.
Trees / Binary Trees
- Tree traversal
Strategy: DFS (recursive or stack)
Note: Pre/In/Post-order
Explanation: Pre: NodeLeftRight, In: LeftNodeRight, Post: LeftRightNode. Implement with recursion or a stack.
- Path sums, subtree sizes
Strategy: DFS with return value
Note: Pass info up
Explanation: Recursively return sums, depths, etc. from children to parent.
- Balanced BST
Strategy: Binary Search Tree
Note: Divide/search logic
Explanation: Recursive or iterative binary search on a tree structure.
Backtracking / Recursion
- All permutations/combinations
Strategy: Backtracking
Note: Try backtrack
Explanation: Choose, explore, undo. Often involves recursion.
- Puzzle solver
Strategy: Backtracking with pruning
Note: Cut invalid branches
Explanation: Add constraints to eliminate impossible paths early.
- Subset/partition problems
Strategy: Recursion + memo
Note: Explore and cache
Explanation: Store (index, current sum) results to avoid recomputation.
Greedy Algorithms
- Max profit / min cost
Strategy: Greedy + Sort
Note: Pick best each time
Explanation: Make locally optimal choice; sort if needed for order.
- Interval scheduling
Strategy: Greedy + Sort
Note: Based on end/start
Explanation: Sort by end time to select most compatible intervals.
- Resource allocation
Strategy: Priority Queue
Note: Track available resources
Explanation: Ex: Meeting rooms, where ending earliest room is reused.
Strings / Parsing
- Palindromes
Strategy: Two Pointers / DP
Note: Expand from center
Explanation: Check equal characters moving inward; or use DP to cache results.
- Longest substring
Strategy: Sliding Window + HashMap
Note: Track seen chars
Explanation: Move left/right bounds of window to maintain uniqueness.
- Regex-style parsing
Strategy: Stack / Recursion
Note: Handle nested patterns
Explanation: Push/pop on brackets or recurse into patterns like (a|b)*.
Math / Bit Manipulation
- Prime numbers
Strategy: Sieve of Eratosthenes
Note: Precompute efficiently
Explanation: Mark non-primes in range; O(n log log n).
- GCD / Power / Modulo
Strategy: Euclidean algo, fast pow
Note: Efficient math ops
Explanation: GCD: gcd(a, b) = gcd(b, a % b). Fast pow: square and reduce.
- Odd-count / single number
Strategy: Bitwise XOR
Note: A^A = 0
Explanation: Use a ^ a = 0, 0 ^ b = b to cancel out duplicates.
