Part XI — Algorithm Paradigms

You have now spent chapters mastering data structures, sorting, searching, graphs, and trees. Those are your building blocks. But when a brand-new problem lands in front of you — one you have never seen before — the question becomes: how do you design a solution?

That is where algorithm paradigms come in. A paradigm is a meta-strategy — a repeatable approach to attacking problems that share structural similarities. Learn four paradigms, and you unlock the ability to tackle thousands of problems, because each paradigm maps a broad class of questions to a known solution shape.

The Four Paradigms

Divide and Conquer

Split the problem, solve the pieces, merge the results.

Divide and conquer takes a problem, breaks it into smaller subproblems of the same type, solves each subproblem recursively, and then combines the results. The subproblems are independent — solving one does not help you solve the other. Merge sort is the textbook example: split the array in half, sort each half, merge the two sorted halves.

The power of divide and conquer lies in the recursion depth. Halving the problem at each step gives you logarithmic depth, which leads to efficient O(n log n) algorithms and excellent parallelism. It works best when the problem splits cleanly and the combine step runs efficiently.

Dynamic Programming

Remember what you’ve already computed.

Dynamic programming (DP) attacks problems where the same subproblems appear over and over again. Unlike divide and conquer, the subproblems overlap — computing Fibonacci(10) requires Fibonacci(9) and Fibonacci(8), but Fibonacci(9) also requires Fibonacci(8). Naïve recursion recomputes identical work exponentially. DP stores each result once and reuses it.

Two properties signal a DP problem: optimal substructure (the optimal solution contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur). When both properties hold, DP transforms exponential brute force into polynomial time.

Greedy Algorithms

Always pick the best local option — and never look back.

Greedy algorithms make a sequence of choices, each time selecting the option that looks best right now, without reconsidering earlier decisions. This works when the problem has the greedy choice property: a locally optimal choice always leads to a globally optimal solution.

The catch? Greedy works only when you can prove that local decisions never need to be revised. When it works, greedy algorithms are breathtakingly simple and efficient. When it doesn’t, they produce wrong answers. The key skill is recognizing which problems satisfy the greedy choice property and which do not.

Recursion and Backtracking

Try everything — but be smart about what you skip.

Backtracking is systematic brute force with pruning. You explore the entire solution space by making a choice, recursing deeper, and then undoing the choice (backtracking) to try alternatives. The “pruning” part is critical: before exploring a branch, you check whether it can possibly lead to a valid solution. If not, you cut it off immediately.

Backtracking handles problems where you need to find all solutions (permutations, combinations, subsets) or a solution that satisfies complex constraints (Sudoku, N-Queens). The time complexity is usually exponential, but aggressive pruning makes it practical for problems of moderate size.

The Decision Tree

When you encounter a new problem, walk through this decision process:

1. Can the problem be decomposed into smaller subproblems of the same type?

• No → The problem requires a different approach (simulation, math, ad hoc).
• Yes → Continue to step 2.

2. Are the subproblems independent or overlapping?

• Independent → Divide and Conquer. Solve each subproblem separately, combine results.
• Overlapping → Continue to step 3.

3. Does the greedy choice property hold?

• Yes → Greedy. Make the locally optimal choice at each step.
• No → Dynamic Programming. Store and reuse subproblem results.

4. Do you need all solutions, or must you satisfy complex constraints?

• Yes → Backtracking. Exhaustive search with pruning.

This decision tree is not a rigid flowchart — many problems can be solved with multiple paradigms. The 0/1 Knapsack problem, for example, tempts you toward greedy (sort by value-to-weight ratio), but the greedy approach fails. You need DP. Recognizing which paradigm fits is one of the highest-value skills you can develop.

Comparing the Paradigms

Aspect	Divide & Conquer	Dynamic Programming	Greedy	Backtracking
Subproblems	Independent	Overlapping	N/A (choices)	Exhaustive
Recomputation	No overlap	Cached	Not applicable	Full exploration
Optimality	Problem-specific	Guaranteed	Needs proof	Finds all/best
Typical complexity	O(n log n)	Polynomial	O(n log n) or O(n)	Exponential
Key technique	Recursion + merge	Memoization/tabulation	Sort + iterate	Choose/explore/undo

What’s Ahead

Each of the next four sub-chapters dives deep into one paradigm:

• Divide and Conquer — the three-step framework, the Master Theorem for analyzing recurrences, and classic problems like maximum subarray, closest pair of points, and count inversions.
• Dynamic Programming — top-down memoization vs. bottom-up tabulation, the five DP patterns (1D, 2D, knapsack, string DP, interval DP), space optimization, and bitmask DP.
• Greedy Algorithms — the exchange argument for proving correctness, activity selection, Huffman coding, fractional knapsack, and the critical question of when greedy fails.
• Recursion and Backtracking — the choose-explore-unchoose template, subsets, permutations, combinations, Sudoku solver, and pruning strategies.

By the end of this part, you will have a reliable mental toolkit for attacking any algorithmic problem. You will recognize the structural patterns that signal each paradigm, implement solutions confidently in Java 25, and — critically — articulate why your approach works to an interviewer.

Let’s start with the paradigm that sits at the foundation of algorithmic thinking: divide and conquer.