Leetcode Categories
Core Algorithm Categories
| Category | Core Idea | Common Clues / Tags | Example Problems |
|---|---|---|---|
| Brute Force | Try every possibility | "Check all combinations", "exhaustive" | Two Sum (naive), Subsets |
| Greedy | Make the best local choice at each step | "Choose max/min now", "no backtracking" | Coin Change (greedy), Activity Selection |
| Divide & Conquer | Split problem into smaller parts | "Divide array", "merge results" | Merge Sort, QuickSort |
| Dynamic Programming (DP) | Store subproblem results to avoid recomputation | "Overlapping subproblems", "optimal substructure" | Fibonacci, Knapsack |
| Backtracking | Try options recursively, undo if needed | "Try all paths", "undo choices" | N-Queens, Sudoku Solver |
| Recursion | Solve by calling itself with smaller input | "Base case", "recursive step" | Factorial, Tree Traversal |
| Graph Algorithms | Traverse or analyze graph structures | "Nodes", "edges", "paths", "cycles" | DFS, BFS, Dijkstra |
| Sliding Window | Move a window across input to find optimal | "Contiguous subarray", "window size" | Max Sum Subarray, Longest Substring |
| Two Pointers | Use two indices to scan input efficiently | "Sorted array", "find pair" | Two Sum (sorted), Palindrome Check |
| Prefix Sum / Hashing | Precompute or track frequency/counts | "Sum range", "count occurrences" | Subarray Sum Equals K |
Tip: Tag each new problem with its category to build a searchable pattern index. Over time, this turns intuition into structure.
Translation of Phrase
Greedy
Asking the robot, it suggests it is when you make a choice from what is provided, regardless of whether it is the most accurate. It implies you don't backtrack. I liked the apple orchard analogy where you are walking through an orchard, and only select apples as you pass and do not go back.
Canonical Coin Systems
Another concept I’ve wrestled with. A canonical coin system means that when you try to make an amount, the number of coins you end up using is the same as if you always picked the biggest coin available first.
Definition
A coin system is canonical if the "largest-coin-first" method (sometimes called greedy) always gives the optimal (fewest coins) solution for every amount.
Canonical Example
Given the coin set [1, 5, 10, 20]:
- To make 16:
- Largest coin that fits: 10
- Then 5, then 1
- Total coins used: 3
- This is also the optimal solution → Canonical
Non-Canonical Example
Given the coin set [1, 3, 4]:
- To make 6:
- Largest coin that fits: 4
- Then 1 + 1 → total of 3 coins
- But the optimal solution is: 3 + 3 → only 2 coins
- So this system is not canonical
Notes
I’ve seen this called "greedy," but that word doesn’t help me much. I prefer to think of it as largest-coin-first. If that method always gives the best result, the system is canonical. If it ever gives a worse result, it’s not.
Greedy
- Interval Scheduling: Greedy works because selecting the activity that finishes earliest leaves the most room for future activities. This satisfies both the greedy-choice property and optimal substructure.
- Coin Change (Greedy): Greedy works only if the coin denominations form a canonical system (e.g., 1, 5, 10, 25). It fails for non-standard sets like [1, 3, 4], where a locally optimal choice may lead to a suboptimal total.
- Huffman Coding: Greedy works because merging the two least frequent symbols at each step builds an optimal prefix code. The structure guarantees minimal total encoding cost.
- Minimum Spanning Tree (Kruskal/Prim): Greedy works due to the optimal substructure and greedy-choice property of MSTs. Choosing the smallest edge that doesn’t form a cycle leads to a globally optimal tree.
- Job Sequencing with Deadlines: Greedy works by scheduling the most profitable job as late as possible within its deadline. This preserves earlier slots for other jobs and maximizes total profit.
- Fractional Knapsack: Greedy works because items can be broken into fractions. Selecting items with the highest value-to-weight ratio yields an optimal solution. This fails for 0/1 knapsack, where items must be taken whole.
Interval Scheduling
Terminology Note
The phrase "select non-overlapping intervals" may be misleading. The input typically contains overlapping intervals, and the goal is to select a subset that does not overlap. A more accurate description would be: "Remove overlapping intervals to produce the largest non-overlapping subset."