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
GreedyGreedy | ||
|---|---|---|
| Use case | Optimization where a locally best choice can be proved safe (exchange argument). | Optimization or counting where choices interact and subproblems repeat. |
| Requirements | Greedy-choice property and optimal substructure; usually a sort. | Optimal substructure and overlapping subproblems; a well-defined state. |
| Time complexity | Typically O(n log n) for the sort, O(n) afterwards. | Number of states times work per transition, e.g. O(n * W) for knapsack. |
| Space complexity | O(1) to O(n). | One entry per state, often reducible to a rolling row. |
| Strengths | Fast, short code, low memory. | Always correct when the recurrence is correct; handles "number of ways" and multi-constraint objectives. |
| Weaknesses | Often wrong: without a proof it silently returns suboptimal answers (coin change with coins 1, 3, 4). | Slower and more memory than greedy; state design is the hard part. |
| Example problems | Non-overlapping intervals, jump game, gas station, fractional knapsack, Huffman coding. | Coin change, 0/1 knapsack, longest increasing subsequence, edit distance. |
| Choose this when | Choose greedy when you can sketch an exchange argument showing the local choice never hurts; if you cannot, do not trust it. | Choose DP when a greedy counterexample exists or the problem asks for counts, or when items cannot be split and choices interact. |