Pattern #25

Divide & Conquer

Important interview questions, thinking patterns, Divide / Solve / Combine lifecycle, Merge Sort, Quick Sort, Binary Search, and Go rules.

Must Solve

15 core questions — solve these first.

1.Merge Sort
Split array in half, sort halves recursively, merge sorted halveseasy
2.Quick Sort
Choose pivot, partition smaller/larger elements, recurse left & rightmedium
3.Binary Search
Check mid, discard unneeded half, log N searcheasy
4.Maximum Subarray
Split left/right & calculate cross-mid contiguous summedium
5.Sort an Array
Efficient O(N log N) sorting using Merge Sort / Quick Sortmedium
6.Kth Largest Element in an Array
QuickSelect partitioning algorithm (O(N) average time)medium
7.Majority Element
Boyer-Moore voting or D&C count majority left/righteasy
8.Search a 2D Matrix II
Top-right corner 2D search eliminationmedium
9.Pow(x, n)
Divide exponent by 2: Pow(x, n/2) * Pow(x, n/2)medium
10.Different Ways to Add Parentheses
Split string by operators & combine sub-resultsmedium
11.Construct Binary Tree from Preorder and Inorder Traversal
Root from preorder, divide inorder left/right subtreesmedium
12.Convert Sorted Array to Binary Search Tree
Pick mid element as root, recurse left & right halveseasy
13.Count of Smaller Numbers After Self
Merge Sort inversion counting with index trackinghard
14.Reverse Pairs
Merge Sort with condition nums[i] > 2*nums[j] during mergehard
15.Count Inversions in an Array
Merge Sort counting split inversion pairsmedium

Also Important

8 more questions worth practicing.

16.Median of Two Sorted Arrays
Binary Search partition across two sorted arrays (O(log(min(M,N))))hard
17.Closest Pair of Points
2D plane vertical line split + strip cross checkhard
18.Merge K Sorted Lists
Divide & Conquer paired list merging or Min-Heaphard
19.Beautiful Array
Construct odd & even sub-arrays recursivelymedium
20.Maximum Binary Tree
Find max index as root, construct left & right subtreesmedium
21.Quad Tree Construction
Split 2D grid into 4 quadrant sub-grids recursivelymedium
22.Karatsuba Multiplication
Fast O(N^1.58) integer multiplication algorithmmedium
23.Strassen Matrix Multiplication
Fast O(N^2.81) matrix multiplication algorithmhard

How to Think

Can I split the input into halves?Divide and Conquer
Can each half be solved independently?Solve left, Solve right, Combine
Problem size becomes half each time?N → N/2 → N/4 (log N levels)
Need sort efficiently?Merge Sort / Quick Sort (O(N log N))
Need search sorted data?Binary Search (O(log N))

Go Divide & Conquer Template

Universal Divide & Conquer Shape in Go

func solve(nums []int) Result {
    // 1. Base Case (stop division)
    if len(nums) <= 1 {
        return baseResult(nums)
    }

    // 2. Divide
    mid := len(nums) / 2

    // 3. Solve Subproblems (Left & Right)
    leftResult := solve(nums[:mid])
    rightResult := solve(nums[mid:])

    // 4. Combine Answers
    return combine(leftResult, rightResult)
}

👉 Total Time: O(N log N) when combine work is O(N) | Space: O(N)

Core 3-Step Lifecycle

1. DIVIDE

Split the main problem into smaller, independent subproblems (usually halves at mid).

2. CONQUER (SOLVE)

Recursively solve the smaller subproblems until reaching base cases (e.g. array size <= 1).

3. COMBINE

Merge subproblem answers into the final result (e.g. 2-pointer sorted merge in Merge Sort).

Divide & Conquer vs Recursion vs Dynamic Programming

Recursion

Any function calling itself. D&C uses recursion, but not all recursion is D&C!

Divide & Conquer

Subproblems are INDEPENDENT (e.g. left half & right half in Merge Sort).

Dynamic Programming

Subproblems OVERLAP repeatedly (e.g. Fibonacci fib(3) & fib(2)). Use Memoization!

Visual Memory Rule

DIVIDE (Split in half)  →  SOLVE (Recurse left & right)  →  COMBINE (Merge results)
Independent Subproblems  →  Divide and Conquer
Overlapping Subproblems  →  Dynamic Programming / Memoization
Binary Search            →  Divide & Discard (No Combine Step Needed!)

💡 Golden Rule: "Break one hard problem into smaller easy problems, solve them, then combine the answers."

Common Interview Mistakes

1. Missing Base Case

Forgetting base case condition leads directly to infinite recursion and call stack overflow crash!

2. Off-by-One Mid Slice Split

Slice indexing errors with mid in Go (nums[:mid] vs nums[mid:]) cause infinite loops.

3. Ignoring Combine Cost

Splitting is fast, but an expensive O(N^2) combine step ruins overall time complexity. Always account for combine cost!

4. Assuming Balanced Split

Quick Sort degrades to O(N^2) if pivot selection repeatedly splits into 0 and N-1 elements instead of balanced halves.

Interview Rules

1. Can split into smaller independent parts? → Divide and Conquer
2. Halve repeatedly? → log₂ N recursion levels
3. Efficient sorting? → Merge Sort (O(N log N)) or Quick Sort
4. Sorted search? → Binary Search (O(log N))
5. Solve left + right? → Recursion with base case
6. Need combine? → Account for combine step complexity
7. Repeated overlapping subproblems? → Use DP / Memoization instead
8. Overall Complexity → O(N log N) time, O(N) space for Merge Sort

Small Rules

Rule 1:Every D&C problem follows: Divide, Solve Recursively, Combine.
Rule 2: Not every problem needs a combine step (Binary Search discards one half directly).
Rule 3: Recurrence T(N) = 2T(N/2) + O(N) yields O(N log N) total time.
Rule 4: Balanced splits (N/2 and N/2) ensure optimal logarithmic depth.
Rule 5: Subproblems MUST be mostly independent; overlapping subproblems require Dynamic Programming.

Production Thinking

Parallel Processing → Run independent left and right half computations concurrently in parallel threads

Large File Chunk Processing → Split multi-gigabyte datasets into Part A, Part B, process separately, and aggregate results

Distributed Systems (MapReduce) → Distribute chunks across worker machines, then combine/aggregate outputs

Search System Elimination → Eliminate large irrelevant search space halves early without scanning all data

Remember This

Divide                → Split problem
Conquer               → Solve smaller parts
Combine               → Build final answer
Half repeatedly       → log n levels
Merge Sort            → Split + Merge
Quick Sort            → Pivot + Partition
Binary Search         → Discard half
Repeated subproblems  → Think DP

💡 Golden Rule: "Break one hard problem into smaller easy problems, solve them, then combine the answers."