CodeWithYash

Intermediate · Module 12 · Lesson 2

Divide and conquer

Split independent subproblems and combine results.

15–25 min readLesson 65 of 123

Lesson 65 of 123

1d streak

Theory lesson · Step-by-step

Understand Divide and conquer

Split independent subproblems and combine results.

Worked approach

Trace the reasoning step by step

  1. 1Define the recursive contract and smallest base case for Divide and conquer.
  2. 2List the choices or independent subproblems available at the current state.
  3. 3Apply one choice, recurse on a strictly smaller state, and combine the result.
  4. 4Undo mutable state before exploring the next sibling branch.
  5. 5Add pruning only when it cannot remove a valid solution.

Concrete example

Find the maximum in [4,1,7,3].

  1. 1Split into two halves.
  2. 2Maxima are 4 and 7.
  3. 3Combine with max(4,7).

The final maximum is 7.

What must remain true (Loop Invariant)

Each call in Divide and conquer owns one well-defined subproblem; on return, its temporary choice is fully undone unless it belongs to the result.

Cost Model

Complexity & Trade-offs

Recursive evaluation
Often O(n log n)
O(log n) stack plus buffers
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Self-similar subproblems, enumeration, constraint solving, and decision trees.
  • Generating combinations and permutations.
  • Converting overlapping recursion into dynamic programming.

Common mistakes

  • Missing a base case or failing to make strict progress.
  • Forgetting to undo shared mutable state.
  • Using exponential search when states repeat and should be memoized.

Practice prompts

  • Reproduce the worked Divide and conquer example without looking at the trace.
  • Change one input condition and explain whether the Divide and conquer invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.