Topic-wise Problem Lists
Code Templates
Algorithm Notes
Dynamic Programming Patterns
DP has several recurring patterns. Identifying the pattern is 80% of solving a DP problem.
- 0/1 Knapsack: Choose items with weight/value constraints
- LCS/LIS: Subsequence problems — O(n²) standard, O(n log n) optimal
- Bitmask DP: State = subset of elements, O(n·2ⁿ)
- Digit DP: Count numbers in [L,R] satisfying property
- Tree DP: DP on rooted tree, process children before parent
- Interval DP: dp[l][r] = optimal answer for subarray [l..r]
Graph Algorithms Cheat Sheet
Core graph algorithms with time/space complexity.
- BFS: Shortest path unweighted — O(V+E)
- Dijkstra: Shortest path non-negative weights — O((V+E) log V)
- Bellman-Ford: Negative weights, detect cycle — O(VE)
- Floyd-Warshall: All-pairs shortest path — O(V³)
- Topological Sort: DAG ordering, cycle detection — O(V+E)
- Kosaraju/Tarjan SCC: Strongly connected components — O(V+E)