Skip to main content

​
Overview

Divide and conquer is a fundamental algorithm design technique that solves problems by:
  1. Dividing the problem into smaller subproblems
  2. Conquering each subproblem recursively
  3. Combining the solutions to solve the original problem
This approach is particularly effective for problems that can be naturally broken down into independent or semi-independent parts.
The divide and conquer technique is the foundation for many classic algorithms like Merge Sort, Quick Sort, and Binary Search.

​
How It Works

The divide and conquer strategy follows a three-step pattern: 
function divideAndConquer(problem) {
  // Base case: problem is small enough to solve directly
  if (problem.isSimple()) {
    return problem.solve();
  }
  
  // Divide: break problem into subproblems
  const subproblems = problem.divide();
  
  // Conquer: recursively solve each subproblem
  const solutions = subproblems.map(sub => divideAndConquer(sub));
  
  // Combine: merge solutions to get final result
  return combine(solutions);
}

​
Common Examples

  • Merge Sort: Divide array in half, sort each half, merge sorted halves
  • Quick Sort: Partition around pivot, sort left and right partitions
  • Binary Search: Divide search space in half each iteration
  • Strassen’s Matrix Multiplication: Divide matrices into smaller blocks

​
Problem 1: Maximum Subarray Sum

Given an array that may contain both positive and negative integers, find the sum of the contiguous subarray with the largest sum.Example:
Input:  [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: The subarray [6, -2, -3, 1, 5] has the maximum sum of 7
The divide and conquer approach considers three possibilities for the maximum subarray:
  1. It lies entirely in the left half
  2. It lies entirely in the right half
  3. It crosses the middle point
We recursively find the maximum for cases 1 and 2, and linearly find the maximum for case 3, then return the maximum of all three.
function middleMaxSum(
  arr: number[],
  left: number,
  middle: number,
  right: number
): number {
  // Find maximum sum starting from middle and going left
  let leftSum = 0;
  let maxLeftSum = Number.MIN_SAFE_INTEGER;
  
  for (let i = middle; i >= left; i--) {
    leftSum += arr[i];
    if (leftSum > maxLeftSum) {
      maxLeftSum = leftSum;
    }
  }

  // Find maximum sum starting from middle+1 and going right
  let rightSum = 0;
  let maxRightSum = Number.MIN_SAFE_INTEGER;
  
  for (let i = middle + 1; i <= right; i++) {
    rightSum += arr[i];
    if (rightSum > maxRightSum) {
      maxRightSum = rightSum;
    }
  }

  // Return the maximum of:
  // 1. Sum crossing the middle
  // 2. Only left side
  // 3. Only right side
  return Math.max(
    maxLeftSum + maxRightSum,
    maxLeftSum,
    maxRightSum
  );
}

function maxSum(arr: number[], left: number, right: number): number {
  // Base case: single element
  if (left === right) {
    return arr[left];
  }

  const middle = Math.floor((left + right) / 2);

  // Return maximum of:
  // 1. Max sum in left half
  // 2. Max sum crossing the middle
  // 3. Max sum in right half
  return Math.max(
    maxSum(arr, left, middle),
    middleMaxSum(arr, left, middle, right),
    maxSum(arr, middle + 1, right)
  );
}

// Usage
const arr = [-2, -5, 6, -2, -3, 1, 5, -6];
const result = maxSum(arr, 0, arr.length - 1); // Returns 7
  • Time Complexity: O(n log n)
    • We divide the array into two halves: O(log n) levels
    • At each level, we do O(n) work to find the crossing maximum
  • Space Complexity: O(log n)
    • Recursion stack depth

​
Problem 2: Inversion Count

Given an array of integers, find the inversion count. An inversion count indicates how far (or close) the array is from being sorted.Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.Example:
Input:  [2, 4, 1, 3, 5]
Output: 3
Explanation: Inversions are (2,1), (4,1), and (4,3)
We can modify merge sort to count inversions efficiently. When merging two sorted subarrays:
  • If an element from the right subarray is smaller than an element from the left subarray, it forms inversions with all remaining elements in the left subarray
  • Count these inversions during the merge process
function merge(
  [leftSubArr, leftSwaps]: [number[], number],
  [rightSubArr, rightSwaps]: [number[], number]
): [number[], number] {
  const arr: number[] = [];
  let i = 0;
  let j = 0;
  let swaps = leftSwaps + rightSwaps;

  while (i < leftSubArr.length && j < rightSubArr.length) {
    if (leftSubArr[i] < rightSubArr[j]) {
      arr.push(leftSubArr[i++]);
    } else {
      arr.push(rightSubArr[j++]);
      // All remaining elements in left subarray form inversions
      // with the current element from right subarray
      swaps += leftSubArr.length - i;
    }
  }

  return [
    [...arr, ...leftSubArr.slice(i), ...rightSubArr.slice(j)],
    swaps,
  ];
}

function getInversionCount(
  [arr, swaps]: [number[], number]
): [number[], number] {
  // Base case: single element has no inversions
  if (arr.length === 1) {
    return [arr, swaps];
  }

  const mid = Math.floor(arr.length / 2);
  
  // Recursively count inversions in left and right halves
  const left = getInversionCount([arr.slice(0, mid), swaps]);
  const right = getInversionCount([arr.slice(mid), swaps]);

  // Merge and count cross inversions
  return merge(left, right);
}

// Usage
const arr = [2, 4, 1, 3, 5];
const [sorted, count] = getInversionCount([arr, 0]);
// sorted: [1, 2, 3, 4, 5]
// count: 3
  • Time Complexity: O(n log n)
    • Same as merge sort - we’re essentially doing a merge sort while counting inversions
  • Space Complexity: O(n)
    • For the temporary arrays created during merging

​
When to Use Divide and Conquer

Use When

  • Problem can be broken into similar subproblems
  • Subproblems are independent
  • Combining solutions is straightforward
  • You need optimal time complexity
  • Problem has natural recursive structure

Avoid When

  • Subproblems overlap significantly (use DP instead)
  • Base cases are too complex
  • Overhead of recursion is too high
  • Problem requires iterative solution
  • Memory constraints are tight

​
Key Characteristics

1

Divide

Break the problem into smaller subproblems of the same type
2

Conquer

Solve the subproblems recursively. If subproblems are small enough, solve them directly (base case)
3

Combine

Merge the solutions of the subproblems to create a solution to the original problem

​
Tips and Best Practices

Define Clear Base Cases: Always identify the simplest case where the problem can be solved directly without further division.
Balance Divisions: For optimal performance, try to divide the problem into equal or nearly equal parts.
Optimize the Combine Step: The efficiency of combining solutions often determines overall algorithm performance.
Watch out for stack overflow with very large inputs. Consider iterative approaches or tail recursion optimization if recursion depth becomes problematic.

​
Comparison with Other Techniques

AspectDivide and ConquerDynamic Programming
SubproblemsIndependentOverlapping
ApproachTop-down (recursive)Bottom-up or top-down
OptimizationNo memoization neededRequires memoization
ExamplesMerge sort, Binary searchFibonacci, LCS

Dynamic Programming

For overlapping subproblems

Greedy Algorithms

For optimization problems

Backtracking

For constraint satisfaction

Build docs developers (and LLMs) love

Get started for freeTalk to us