Greedy & Backtracking
Greedy algorithms and backtracking sit at opposite ends of a spectrum. Greedy makes the locally optimal choice at each step and never looks back. Backtracking tries every possibility systematically and undoes choices that do not work. Knowing when to use each — and when neither is the right tool — is a key interview skill.
Greedy Algorithms
A greedy algorithm builds a solution incrementally, choosing the best option at each step without reconsidering past choices. It works when the problem has the greedy choice property: a locally optimal choice at each step leads to a globally optimal solution.
When greedy works:
- The problem has optimal substructure (same as DP)
- Making the best local choice does not prevent finding the
global optimum
- You can prove (or at least argue convincingly) that greedy
gives the correct answer
When greedy fails:
- The locally optimal choice leads to a dead end
- You need to consider combinations or sequences of choices
- A counterexample exists where greedy gives the wrong answer
The critical question in an interview: "How do I know greedy works here?" You should either provide an argument (exchange argument, stays-ahead argument) or acknowledge that it requires proof and state why you believe it works.
Interval Scheduling
The classic greedy problem. Given a set of intervals (start, end), find the maximum number of non-overlapping intervals.
Problem: Activity selection.
Intervals: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11)]
Greedy strategy: Always pick the interval that ends earliest.
Sort by end time:
(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11)
Pick (1,4). Next compatible: (5,7). Pick it.
Next compatible: (8,11). Pick it.
Result: 3 intervals.
Why it works: Picking the earliest-ending interval leaves the
most room for future intervals. Any other choice either picks
the same number or fewer.
def max_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count = 0
last_end = -infinity
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
Time: O(n log n) for sorting. Space: O(1) beyond the sort.
Interval Merging & Minimum Removals
Related problems that use sorting + greedy:
Problem: Minimum number of intervals to remove to eliminate all overlaps.
Answer: total intervals - max non-overlapping intervals.
Use the activity selection algorithm above.
Problem: Merge overlapping intervals.
Sort by start time. Merge greedily:
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
Jump Game
Problem: Given an array where arr[i] is the max jump length from
position i, can you reach the last index?
Greedy: Track the farthest position you can reach.
farthest = 0
for i in range(len(arr)):
if i > farthest:
return False # can't reach this position
farthest = max(farthest, i + arr[i])
return True
Time: O(n). Space: O(1).
Huffman Coding
A greedy algorithm for constructing optimal prefix codes. While rarely asked to implement in full, understanding the principle matters:
Strategy: Always merge the two lowest-frequency nodes first.
This works because assigning shorter codes to more frequent
symbols minimizes total encoded length. Each merge step
optimally combines the two cheapest remaining options.
Task Scheduling
Problem: Given tasks with deadlines and penalties, schedule to
minimize total penalty.
Greedy: Sort by deadline. Schedule each task as late as possible.
Problem: Given tasks that take 1 unit of time each with profits
and deadlines, maximize profit.
Greedy: Sort by profit (descending). For each task, schedule it
in the latest available slot before its deadline.
When Greedy Fails
Greedy is tempting because it is simple. But it fails on many problems where it looks like it should work:
Problem: Coin change (arbitrary denominations).
Coins: [1, 3, 4], target: 6
Greedy (largest coin first): 4 + 1 + 1 = 3 coins
Optimal: 3 + 3 = 2 coins
Greedy fails because taking the largest coin does not always
lead to the fewest total coins. This requires DP.
Problem: 0/1 Knapsack.
Greedy by value/weight ratio does not work for 0/1 knapsack
(it works for fractional knapsack, where you can take partial items).
If you suspect greedy might work but are not sure, try a small counterexample. If you find one, switch to DP or backtracking.
Backtracking
Backtracking is systematic trial and error. It explores all possible solutions by making choices, checking constraints, and undoing choices that violate constraints. It is essentially DFS on the solution space tree.
Backtracking template:
def backtrack(state, choices):
if is_complete(state):
record_solution(state)
return
for choice in choices:
if is_valid(state, choice):
make_choice(state, choice)
backtrack(state, remaining_choices)
undo_choice(state, choice) # the "backtrack" step
The key insight: the undo step restores the state so the next choice starts fresh. This is what makes backtracking different from plain recursion — you explicitly manage and restore state.
Permutations
Problem: Generate all permutations of [1, 2, 3].
def permutations(nums):
result = []
def backtrack(current, remaining):
if not remaining:
result.append(current[:]) # copy, not reference
return
for i in range(len(remaining)):
current.append(remaining[i])
backtrack(current, remaining[:i] + remaining[i+1:])
current.pop() # undo
backtrack([], nums)
return result
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Time: O(n! * n). Space: O(n) for the recursion stack.
Subsets
Problem: Generate all subsets of [1, 2, 3].
def subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:]) # every state is a valid subset
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
Time: O(2^n * n). Space: O(n).
N-Queens
The canonical backtracking problem. Place N queens on an N x N board so no two attack each other.
def solve_n_queens(n):
result = []
board = [['.' for _ in range(n)] for _ in range(n)]
def is_safe(row, col):
# Check column
for r in range(row):
if board[r][col] == 'Q':
return False
# Check upper-left diagonal
r, c = row - 1, col - 1
while r >= 0 and c >= 0:
if board[r][c] == 'Q':
return False
r -= 1
c -= 1
# Check upper-right diagonal
r, c = row - 1, col + 1
while r >= 0 and c < n:
if board[r][c] == 'Q':
return False
r -= 1
c += 1
return True
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if is_safe(row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.' # undo
backtrack(0)
return result
Optimization: Use sets to track occupied columns and diagonals
instead of scanning the board each time. This improves is_safe
from O(n) to O(1).
Sudoku Solver
def solve_sudoku(board):
def is_valid(board, row, col, num):
# Check row, column, and 3x3 box
for i in range(9):
if board[row][i] == num:
return False
if board[i][col] == num:
return False
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if board[r][c] == num:
return False
return True
def backtrack():
for row in range(9):
for col in range(9):
if board[row][col] == '.':
for num in '123456789':
if is_valid(board, row, col, num):
board[row][col] = num
if backtrack():
return True
board[row][col] = '.' # undo
return False # no valid number -> backtrack
return True # all cells filled
Pruning: Making Backtracking Practical
Raw backtracking explores an exponential number of states. Pruning eliminates branches early by detecting that they cannot lead to a valid solution.
Types of pruning:
Constraint pruning: Skip choices that violate constraints immediately.
(N-queens: skip columns already occupied)
Bound pruning: Skip branches where the best possible outcome is
worse than the current best known solution.
(Branch and bound: if remaining items cannot improve on current max)
Symmetry pruning: Skip branches that are mirror images of already-
explored branches.
(N-queens: only explore half the first row due to symmetry)
Ordering heuristic: Try the most constrained choices first.
(Sudoku: fill the cell with fewest candidates first)
Pruning can reduce backtracking from impractical to fast:
N-Queens without pruning: Explores n^n states
N-Queens with column/diagonal pruning: Explores far fewer
n=8: ~15,000 states instead of ~16 million
n=12: ~850,000 states instead of ~8 billion
Greedy vs DP vs Backtracking
Approach When to use Time
──────────────────────────────────────────────────────────────
Greedy Local optimal = global optimal Usually O(n log n)
DP Overlapping subproblems, Polynomial
optimal substructure
Backtracking Need all solutions, or Exponential (with pruning
constraint satisfaction often much less)
Decision process:
1. Can I prove greedy works? -> Use greedy (fastest)
2. Does greedy fail? Are subproblems overlapping? -> Use DP
3. Need all solutions or no polynomial structure? -> Use backtracking
Real-World Applications
Greedy algorithms appear in:
- Network routing (Dijkstra's algorithm is greedy)
- Compression (Huffman coding)
- Task scheduling in operating systems
- Resource allocation with simple constraints
- Making change with standard coin denominations
Backtracking appears in:
- Constraint satisfaction (Sudoku, crossword generation)
- Combinatorial optimization (traveling salesman heuristics)
- Game AI (chess move exploration with alpha-beta pruning)
- Regular expression matching
- Compiler optimization (register allocation)
Common Pitfalls
- Assuming greedy works without verification: Greedy is wrong more often than it is right. Always try a counterexample before committing to a greedy approach in an interview.
- Forgetting to undo in backtracking: The undo step (
current.pop(),board[row][col] = '.') is the defining feature of backtracking. Forgetting it means your state accumulates choices from all branches. - Not copying solutions: When you find a valid solution in backtracking, append a copy (
current[:]), not a reference. Otherwise, all entries in your result list point to the same (eventually empty) list. - Missing pruning opportunities: Raw backtracking is often too slow. Look for ways to eliminate branches early — check constraints before recursing, not after.
- Confusing subsets and permutations: Subsets use a
startindex to avoid duplicates. Permutations use aremainingset. Mixing these up produces wrong results. - Not handling duplicates in backtracking: If the input has duplicates, sort it first and skip consecutive equal elements at the same recursion level to avoid duplicate solutions.
- Using backtracking when DP works: If the problem asks for a count or an optimum (not all solutions), DP is almost always better than backtracking. Backtracking is for enumeration and constraint satisfaction.
Key Takeaways
- Greedy works when local optimal equals global optimal. The proof is important — without it, you are guessing. Try counterexamples before committing.
- Interval scheduling (sort by end time, pick greedily) is the most important greedy pattern for interviews. Know it cold.
- Backtracking is DFS on the solution space. The template is: choose, explore, undo. Every backtracking problem follows this structure.
- Pruning transforms exponential backtracking into something practical. Always look for constraints you can check before recursing, not after.
- Permutations, subsets, and N-queens are the three backtracking problems you must be able to write from memory. They cover the major patterns: arrangements, selections, and constraint satisfaction.
- When in doubt: try greedy first (fast and simple). If it fails, check if DP applies (polynomial). If you need all solutions, use backtracking (exponential but complete).