All Roadmapsโ€บ๐Ÿง  Data Structures & Algorithmsโ€บPhase 3โ€บDivide and Conquer

Divide and Conquer

0/12 in this phase0/57 across the roadmap

๐Ÿ“– Concept

Divide and Conquer breaks a problem into smaller sub-problems, solves each independently, then combines the results. It's the foundation of merge sort, quicksort, binary search, and many efficient algorithms.

Three steps:

  1. Divide โ€” Split the problem into smaller sub-problems
  2. Conquer โ€” Solve each sub-problem recursively (or directly if small enough)
  3. Combine โ€” Merge the sub-solutions into the final answer

Classic D&C algorithms:

  • Merge Sort โ€” Divide array in half, sort each, merge โ†’ O(n log n)
  • Quick Sort โ€” Partition around pivot, sort each side โ†’ O(n log n) avg
  • Binary Search โ€” Divide search space in half โ†’ O(log n)
  • Karatsuba Multiplication โ€” Multiply large numbers faster โ†’ O(n^1.585)
  • Closest Pair of Points โ€” Find nearest pair โ†’ O(n log n)
  • Strassen's Matrix Multiplication โ€” Faster matrix multiply โ†’ O(n^2.807)

Master Theorem for analyzing D&C recurrences: T(n) = aT(n/b) + O(nแตˆ)

  • If d < log_b(a): T(n) = O(n^(log_b(a)))
  • If d = log_b(a): T(n) = O(nแตˆ log n)
  • If d > log_b(a): T(n) = O(nแตˆ)

๐Ÿ  Real-world analogy: Organizing a library. Split all books into A-M and N-Z (divide), organize each group (conquer), then put them together on the shelf (combine). Each group can be further split.

๐Ÿ’ป Code Example

codeTap to expand โ›ถ
1// MERGE SORT โ€” Classic D&C
2function mergeSort(arr: number[]): number[] {
3  if (arr.length <= 1) return arr;     // Base case
4

5  const mid = Math.floor(arr.length / 2);
6  const left = mergeSort(arr.slice(0, mid));   // Divide
7  const right = mergeSort(arr.slice(mid));      // Divide
8

9  return merge(left, right);                    // Combine
10}
11

12function merge(left: number[], right: number[]): number[] {
13  const result: number[] = [];
14  let i = 0, j = 0;
15  while (i < left.length && j < right.length) {
16    if (left[i] <= right[j]) result.push(left[i++]);
17    else result.push(right[j++]);
18  }
19  return [...result, ...left.slice(i), ...right.slice(j)];
20}
21

22// COUNT INVERSIONS โ€” Merge sort modification
23function countInversions(arr: number[]): number {
24  if (arr.length <= 1) return 0;
25  const mid = Math.floor(arr.length / 2);
26  const left = arr.slice(0, mid);
27  const right = arr.slice(mid);
28  let count = countInversions(left) + countInversions(right);
29

30  let i = 0, j = 0, k = 0;
31  while (i < left.length && j < right.length) {
32    if (left[i] <= right[j]) { arr[k++] = left[i++]; }
33    else {
34      arr[k++] = right[j++];
35      count += left.length - i; // All remaining left elements form inversions
36    }
37  }
38  while (i < left.length) arr[k++] = left[i++];
39  while (j < right.length) arr[k++] = right[j++];
40  return count;
41}
42

43// MAXIMUM SUBARRAY โ€” D&C approach (Kadane's is simpler, but this shows D&C)
44function maxSubarrayDC(arr: number[], lo: number, hi: number): number {
45  if (lo === hi) return arr[lo];
46

47  const mid = Math.floor((lo + hi) / 2);
48  const leftMax = maxSubarrayDC(arr, lo, mid);
49  const rightMax = maxSubarrayDC(arr, mid + 1, hi);
50  const crossMax = maxCrossing(arr, lo, mid, hi);
51

52  return Math.max(leftMax, rightMax, crossMax);
53}
54

55function maxCrossing(arr: number[], lo: number, mid: number, hi: number): number {
56  let leftSum = -Infinity, sum = 0;
57  for (let i = mid; i >= lo; i--) { sum += arr[i]; leftSum = Math.max(leftSum, sum); }
58  let rightSum = -Infinity; sum = 0;
59  for (let i = mid + 1; i <= hi; i++) { sum += arr[i]; rightSum = Math.max(rightSum, sum); }
60  return leftSum + rightSum;
61}
62

63// POWER โ€” D&C O(log n)
64function power(base: number, exp: number): number {
65  if (exp === 0) return 1;
66  if (exp < 0) return 1 / power(base, -exp);
67  const half = power(base, Math.floor(exp / 2));
68  return exp % 2 === 0 ? half * half : half * half * base;
69}

๐Ÿ‹๏ธ Practice Exercise

Practice Problems:

  1. Implement merge sort and count the number of comparisons
  2. Count inversions in an array using modified merge sort
  3. Find maximum subarray sum using divide and conquer
  4. Implement power(x, n) in O(log n) using D&C
  5. Find the closest pair of points in a 2D plane
  6. Multiply two large numbers using Karatsuba algorithm (conceptual)
  7. Find kth largest element using quickselect (average O(n))
  8. Construct a binary tree from preorder and inorder traversal
  9. Find the majority element using D&C (Boyer-Moore is better, but practice D&C)
  10. Skyline problem โ€” merge skylines from two halves

โš ๏ธ Common Mistakes

  • Not identifying the base case โ€” D&C needs a base case for the smallest sub-problem

  • Inefficient combining step โ€” the combine step can dominate complexity if not optimized

  • Creating too many new arrays (memory overhead) โ€” in-place D&C is often preferred

  • Using D&C when a simpler approach exists โ€” Kadane's O(n) beats D&C O(n log n) for max subarray

  • Not applying the Master Theorem to analyze complexity โ€” essential for understanding D&C performance

๐Ÿ’ผ Interview Questions

๐ŸŽค Mock Interview

Practice a live interview for Divide and Conquer

โ† PreviousFast & Slow Pointers (Floyd's Cycle Detection)Next โ†’Backtracking โ€” Permutations, Combinations, Subsets