Divide and Conquer: Ownership, Progress, and Recombination

Reader guide and study workflow · Complete course map

A recursive algorithm needs an exact subproblem boundary, a decreasing size, and a combine rule that preserves the result contract. A heap merge offers a useful contrast: it maintains a stream frontier instead of recursively splitting.

Prerequisites and readiness

Know inorder traversal, height balance, linked-list pointer rewiring, merging sorted streams, and square-grid coordinates. Be able to state what data one recursive call owns and how its children partition that data.

Reasoning workshop: a recursive call must own something precise

Ranges become balanced trees

For sorted keys [-10,-3,0,5,9], choose 0 and give the two keys before it to the left child and the two after it to the right child. The midpoint is excluded from both child ranges. Induction then has two separate jobs: prove ordering from the sorted ranges and prove balance from their sizes. A test that checks only inorder misses an unbalanced chain; a test that checks only balance misses a misplaced key.

Even-length ranges may use either middle key while still producing a balanced BST. The reference uses the lower midpoint, but the problem accepts any valid balanced output. The problem requires strictly increasing input: distinct keys make every left key strictly smaller and every right key strictly larger. Duplicate-key placement would require a different, explicitly defined BST policy.

A linked-list boundary is a cut, not an index

For list 4->2->1->3, slow/fast traversal locates the second half at 1. Setting the predecessor’s Next to nil creates two actual chains, 4->2 and 1->3. Without that cut, the left recursive call still sees the original full list and does not shrink. Sort both smaller lists, then merge them by repeatedly taking the smaller head.

The merge invariant is a sorted output prefix containing exactly the consumed nodes. Reusing nodes preserves identity and avoids replacement-node allocation. Taking from the left on equality retains stability. For validation, capture the original pointer set, traverse the result with cycle detection, and check that the same nodes occur exactly once in sorted order. Correct-looking values alone cannot detect lost or duplicated identities.

Pairwise merge and heap merge are alternatives, not the same implementation

A divide-and-conquer solution can merge k lists pairwise through logarithmically many rounds. The supplied reference instead stores one current head per nonempty list in a min-heap. For [1,4], [1,3], [2], the initial frontier is 1,1,2. Popping the first 1 reveals 4, but other stream heads still compete before 4 can be emitted.

Both approaches exploit sorted subresults and can achieve O(N log k), but the heap version uses O(h) active entries for h nonempty lists. Scanning k supplied heads still costs O(k), even if most are nil. The lists must be disjoint; a shared tail would represent the same node more than once and invalidate a naïve merge’s identity accounting.

A quad tree compresses only proven uniformity

For [[1,1],[1,0]], one differing cell forces a split. Child order is top-left, top-right, bottom-left, bottom-right, with values true,true,true,false. A leaf represents every cell of its owned region, so a majority test cannot justify compression. A positive power-of-two size guarantees exact halves until size one.

A direct uniformity scan at each recursion level has a safe O(n² log n) upper bound; a prefix-sum uniformity query can reduce repeated scanning, but introduces preprocessing and additional storage. The reference retains direct scans because the representation and proof are simple. Internal Val remains true by existing convention; only leaf values describe pixel values. Validation should expand the tree back to the original grid and verify that homogeneous regions are leaves.

Reconstruct the recurrence from actual work

Balanced BST construction does O(1) node work per element: O(n). List merge sort performs O(n) splitting/merging work per level across O(log n) levels: O(n log n), with recursion rather than O(1) auxiliary space. Quad-tree scans may repeat region inspection. Naming all of them “divide and conquer” does not give them the same recurrence or memory behavior.

Reconstruction lab and answer key

Convert Sorted Array to Binary Search Tree

For sorted keys [2,5,8,11,14,17], consider midpoint roots 8 and 11. Can both work? A third construction chooses 5, with one key on the left and four balanced keys on the right. Why does sorted inorder alone fail to certify that third root?

Model answer

Either midpoint yields child sizes 2 and 3, whose balanced constructions have height 2, so both are valid. Root 5 has a height-1 left child and a four-node balanced right subtree of height 3, violating the permitted difference of one. All three can preserve inorder; only a per-node height check establishes balance.

Sort List

Distinct nodes arrive as P(2)→Q(1)→R(2)→S(1). Give the stable sorted identity order. Would rewriting their values to 1,1,2,2 while retaining P→Q→R→S satisfy this exercise?

Model answer

The stable order is Q→S→P→R. Equal-valued nodes retain their original relative order, and each original node keeps its own value. Rewriting values changes what a caller’s pointer to P or Q observes and violates the node-preserving contract even though the printed value sequence looks sorted. Sorting must rewire links.

Merge k Sorted Lists

Four list lengths are [4,1,1,1]. Charge a merge of nonempty lengths a,b exactly a+b units and forwarding an unpaired run zero. Compare adjacent balanced rounds with left-to-right sequential merging. Why do these totals not determine actual pointer comparison counts?

Model answer

Balanced rounds cost (4+1)+(1+1)=7, followed by 5+2=7, for 14 units. Sequential merging costs 5+6+7=18 units. The model charges all tail nodes; a pointer merge can attach a remaining tail without one comparison per node. Values and implementation determine actual comparisons, so these accounting totals are not timing measurements.

Construct Quad Tree

A quad tree represents [[0,1],[0,0]] correctly. A learner swaps its TopRight and BottomLeft child pointers while keeping the same leaf values and node count. What grid does it represent afterward, and which validation detects the defect?

Model answer

It now represents [[0,0],[1,0]]. Quadrant positions are semantic, so the multiset of leaf values and total node count are insufficient. Expand leaves into their owned grid coordinates and compare every cell. Uniformity compression is a separate check: a correct image represented by unnecessary subdivisions can still violate the canonical leaf contract.

Problems in this module

• Convert Sorted Array to Binary Search Tree
• Sort List
• Merge k Sorted Lists
• Construct Quad Tree

Interactive checkpoint

Open the Divide & Conquer quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Supplementary workbook and model answers

Divide & Conquer Workbook

This workbook is intentionally more guided than a normal problem set. The goal is to train the algorithmic reflex: contract first, code second.

---

Drill 1: Write the contract

For each function, write one sentence of the form:

f(boundary) returns ... for exactly ...

A. build(lo, hi) for a sorted array

Expected contract:

build(lo, hi) returns the root of a height-balanced BST containing exactly nums[lo..hi].

B. sort(head) for a linked list

Expected contract:

sort(head) returns a sorted linked list containing exactly the nodes reachable from head.

C. build(r0, c0, size) for a grid

Expected contract:

build(r0, c0, size) returns a quad-tree node representing exactly the square with top-left (r0,c0) and side length size.

---

Drill 2: Boundary accounting

For each split, verify that every item appears exactly once.

Inclusive array range

Parent:

lo..hi

Split:

lo..mid-1
mid
mid+1..hi

Check:

• Nothing before lo appears.
• Nothing after hi appears.
• mid appears once.
• No index appears in both children.

Quad tree square

Parent:

(r0, c0, size)

Split:

(r0,      c0,      half)
(r0,      c0+half, half)
(r0+half, c0,      half)
(r0+half, c0+half, half)

Check the four quadrants visually on a 4 x 4 grid.

---

Drill 3: Fix the bug

Buggy sorted-array split

mid := (lo + hi) / 2
root.Left = build(lo, mid)
root.Right = build(mid+1, hi)

Question: What goes wrong?

Answer: mid is included in the left child even though it is already used as root. For a one-element range, build(lo, mid) repeats the same range forever.

Correct split:

root.Left = build(lo, mid-1)
root.Right = build(mid+1, hi)

Buggy linked-list split

slow, fast := head, head
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
}
left := SortList(head)
right := SortList(slow)

Question: What goes wrong?

Answer: The list was never cut. left may still contain the entire original list, so recursion does not shrink correctly.

Correct contract: for a list with at least two nodes, retain the node immediately before slow, cut its Next link, and recurse on the two detached chains. The complete split reasoning is in the model answers below.

---

Drill 4: Recursion tree cost

For each recurrence, state the runtime.

A.

T(n) = 2T(n/2) + O(1)

Answer: O(n). There are n leaves and constant work per internal node.

B.

T(n) = 2T(n/2) + O(n)

Answer: O(n log n). Each level costs O(n), and there are O(log n) levels.

C.

T(n, k) = O(n) per merge round, O(log k) rounds

Answer: O(n log k).

---

Original practice problems

These are not meant to replace the curated interview problems. They are designed to isolate skills.

1. Validate a recursive boundary log

You are given a log of calls from a divide-and-conquer function over an inclusive array range:

build(0, 6)
build(0, 2)
build(0, 0)
build(2, 2)
build(4, 6)
build(4, 4)
build(6, 6)

Determine whether the function could be choosing the midpoint as root and recursing on left and right ranges. Explain which indices became roots.

Expected insight: roots are 3,1,0,2,5,4,6.

2. Merge-round simulator

Given list lengths:

[10, 1, 1, 1, 1]

Compute the total number of nodes touched by sequential merging versus balanced pairwise merging. This reveals why balanced merging matters.

3. Quad region classifier

Given a prefix-sum matrix and a region (r0,c0,size), write a helper:

func regionSum(ps [][]int, r0, c0, size int) int

Then classify the region as all zero, all one, or mixed.

4. Bottom-up linked-list merge sort

Rewrite SortList iteratively. This removes recursion stack usage but requires careful sublist cutting. This is a professional extension after mastering the recursive version.

5. Compare heap merge and pairwise merge

Implement both MergeKLists strategies. Add counters for comparisons. Generate cases where one performs fewer comparisons in practice even though both are O(n log k).

---

Review questions

1. Why is an inorder-only test insufficient for sorted-array-to-BST?
2. Why does merge sort fit linked lists better than quicksort?
3. Why can sequentially merging k lists degrade to O(k*n)?
4. What does Val mean for a non-leaf quad-tree node?
5. How does a 2D prefix sum improve quad-tree construction?
6. What must be true about subproblems for divide-and-conquer to be appropriate?
7. How do you prove that a split has no gaps and no overlaps?
8. What is the difference between divide-and-conquer and dynamic programming?

Complete model answers and cost conventions

Drill 3: complete list-split reasoning

The displayed buggy list code is intentionally a counterexample, not a valid implementation. A correct top-down split first returns for an empty or one-node list. For longer lists, advance slow by one and fast by two while retaining the node immediately before slow. Cut prev.Next = nil, then recursively sort the two now-disjoint chains. The base case guarantees prev is nonnil when the cut is performed. Both children contain fewer nodes than the parent, and no original node is duplicated or lost.

Practice 1: recursive boundary log

The log is valid for midpoint roots. The root indices in preorder are 3,1,0,2,5,4,6. At the first call, [0,6] splits into [0,2], root 3, and [4,6]. Repeating this argument proves exact coverage and explains why empty child ranges need not appear in the log. It does not prove that a particular implementation terminates on every possible range; the decreasing-size argument supplies that separate obligation.

Practice 2: merge-round simulator

Use this explicit accounting model: merging two nonempty lists of lengths a and b costs a+b node-units, including all tail nodes; forwarding an unpaired list costs zero. The lengths alone do not determine actual comparison counts because a pointer implementation can attach a remaining tail at once.

For [10,1,1,1,1], sequential left-to-right merging costs 11+12+13+14=50 units. Balanced adjacent rounds cost (11+2)+13+14=40 units: the first round produces [11,2,1], the second [13,1], and the third [14]. “Balanced rounds” fixes the pairing schedule; a size-priority merge schedule is a different strategy and can have another total. This example establishes the accounting difference without pretending to be a timing benchmark.

Practice 3: complete region-sum helper

Let ps have one extra zero row and column, so ps[r][c] sums grid rows before r and columns before c. Build it using cell+above+left-diagonal. Then:

func regionSum(ps [][]int, r0, c0, size int) int {
    r1, c1 := r0+size, c0+size
    return ps[r1][c1] - ps[r0][c1] - ps[r1][c0] + ps[r0][c0]
}

The queried square must lie inside the original rectangular grid. For binary cells, sum zero means all zero, sum==size*size means all one, and any intermediate sum means mixed. This uses nonnegative binary values: cancellation would make the same uniformity test invalid for arbitrary signed cells. After O(n²) prefix preprocessing, each square’s classification is O(1); a full canonical quadtree has O(n²) nodes.

Practice 4: bottom-up list merge sort model

Count n nodes. For run widths 1,2,4,... smaller than n, scan the chain through a dummy output head. Cut a left run of at most width nodes, then a right run of at most width nodes, saving the next unprocessed head. Merge the two detached runs by repeatedly linking the smaller head, choosing left on ties for stability; attach the remaining tail and retain the merged tail for the next pair. Continue until the pass consumes every node, then use the dummy’s next as the next pass’s head. A cut advances at most width nodes and writes the final Next to nil. Every pass consumes and emits each original node exactly once, and the maximum sorted run length doubles. O(n log n) time and O(1) auxiliary pointer state, excluding the existing nodes; no recursive stack is required.

Practice 5: comparison experiment model

Instrument value comparisons only, not heap-index checks or nil checks, and keep that definition identical between implementations. Test interleaved equal-length lists, disjoint value ranges, many empty lists, and one long list plus tiny lists. Pairwise merging can attach a wholly remaining tail without further value comparisons; a heap repeatedly repairs its frontier. Conversely, pairing schedule and data interleaving alter pairwise work. Report exact input values, k, total nodes N, strategy, comparison count, and output verification before making a claim. Both can be O(N log k) in the usual multi-nonempty-list worst case, but one measurement does not prove a universal winner.

Review-question answer key

1. Inorder alone is insufficient. A skewed tree can have the correct inorder values but violate the height-balance requirement. Check every node’s left/right height difference and exact multiset coverage in addition to ordering.
2. Why merge sort fits lists. Sequential merging and pointer cuts do not need random access. Quicksort partitioning can be implemented on lists, but array-style in-place index swapping and random pivot access do not transfer directly. This is a fit argument, not a claim that list quicksort is impossible.
3. Sequential k-list degradation. An early long merged prefix can be scanned again for each later list. With k lists and N total nodes, repeated rescanning can reach O(kN), whereas balanced merge levels expose each node only O(log k) times in the full-scan model.
4. Nonleaf Val. Children determine a nonleaf quad node’s represented region; its own Val is not a uniform-cell value. This pack’s reference sets nonleaf Val=true, and that observable convention is preserved even though region semantics do not depend on it.
5. Prefix sums. They replace scanning every cell of a region with four table accesses and arithmetic. The preprocessing and total node count remain O(n²); this can improve a region-scanning O(n² log n) upper bound to O(n²) construction work.
6. Suitable subproblems. Boundaries must be precise, children must shrink toward bases, recursive contracts must be sufficient for combination, and the cost of splitting/combining must be acceptable. Independent child solutions are particularly natural; overlapping subproblems may invite memoization instead of repeated recursion.
7. No gaps or overlaps. Show that child sets plus any separately handled root partition the parent: their union equals the parent and every pair is disjoint. For inclusive array ranges, use [lo,mid-1], {mid}, [mid+1,hi]. For quadrants, partition each coordinate range into two disjoint halves and take their four Cartesian products.
8. Divide and conquer versus DP. Divide and conquer recursively solves pieces and combines their answers. DP reuses answers to repeated states so overlapping work is not recomputed. They can coexist—for example, recursion plus memoization—so the distinction is about repeated subproblems and reuse, not whether code contains recursion.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Divide & Conquer Foundations (Interview 150)

Mental model

Core patterns

Pattern: Split by middle

Pattern: Sort then merge

Pattern: Pairwise merging

Pattern: Uniform-region compression

When to reach for this module

Common failures

Learner experience: how to make this topic stick