Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
| Use case | Top-down DP: write the natural recursion and cache results. | Bottom-up DP: fill the table in dependency order. |
| Requirements | A cache keyed by state (dict or array) and enough recursion depth. | A topological order of states, usually simple increasing indices. |
| Time complexity | Same asymptotics as tabulation; only reachable states are computed. | Same asymptotics; computes every state, even unreachable ones. |
| Space complexity | Cache plus O(depth) call stack. | Table only, often shrunk to O(1) or O(min(m, n)) rows. |
| Strengths | Direct translation from the recurrence; skips unreachable states; easy with irregular state spaces. | No recursion; better constants and cache behaviour; space optimization is natural. |
| Weaknesses | Recursion overhead and stack-overflow risk; harder to reduce space to a rolling row. | Must know the evaluation order in advance; wastes work on unneeded states. |
| Example problems | Word break, longest increasing path in a matrix, burst balloons. | Climbing stairs, unique paths, coin change, longest common subsequence. |
| Choose this when | Choose memoization when the recursion is easier to see than the fill order, or when only a fraction of the state space is reachable. | Choose tabulation when the state order is obvious, recursion depth would be large, or you need the rolling-array space optimization. |