Divide & Conquer

Divide & Conquer is an algorithmic paradigm that breaks a complex problem down into multiple smaller, structurally identical subproblems.

It involves three distinct steps:

1. Divide: Break the given problem into subproblems of the same type.
2. Conquer: Recursively solve these subproblems.
3. Combine: Merge the answers of the subproblems to form the final answer.

Real-Life Analogy

Think of Counting Votes in a National Election. Instead of one person counting 150 million votes (which would take years), the problem is Divided:

1. Each state counts its own votes.
2. But each state Divides the problem further: Each county counts its own votes.
3. Each county Divides the problem: Each polling station counts its own votes.

Once the polling station finishes (Conquers), it sends the total to the county. The county Combines the station totals and sends it to the state. The state Combines the county totals.

Classic Examples

We have already seen two incredibly famous Divide & Conquer algorithms in the Sorting module:

• Merge Sort: Divides the array in half, recursively sorts both halves, and then Combines them in a merge() function.
• Quick Sort: Chooses a pivot, partitions the array into two smaller arrays, and recursively sorts them.

Advanced Example: Maximum Subarray Sum

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. (This can be solved in $O(N)$ with Kadane's algorithm, but it is a classic D&C interview question).

If we divide the array in half, the maximum subarray MUST lie in one of three places:

1. Entirely in the Left half.
2. Entirely in the Right half.
3. Crossing the midpoint (spanning across both halves).

function maxSubArrayDivideAndConquer(nums: number[]): number {
  return findMax(nums, 0, nums.length - 1);
}

function findMax(nums: number[], left: number, right: number): number {
  if (left === right) return nums[left]; // Base case
  
  const mid = Math.floor((left + right) / 2);
  
  // Divide and Conquer
  const leftMax = findMax(nums, left, mid);
  const rightMax = findMax(nums, mid + 1, right);
  
  // Combine (Calculate the crossing max)
  const crossMax = findCrossingMax(nums, left, mid, right);
  
  return Math.max(leftMax, rightMax, crossMax);
}

function findCrossingMax(nums: number[], left: number, mid: number, right: number): number {
  let leftSum = -Infinity;
  let currentSum = 0;
  for (let i = mid; i >= left; i--) {
    currentSum += nums[i];
    leftSum = Math.max(leftSum, currentSum);
  }
  
  let rightSum = -Infinity;
  currentSum = 0;
  for (let i = mid + 1; i <= right; i++) {
    currentSum += nums[i];
    rightSum = Math.max(rightSum, currentSum);
  }
  
  return leftSum + rightSum;
}

Time Complexity (Master Theorem)

To analyze the Time Complexity of Divide & Conquer algorithms, we use the Master Theorem: $$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$

• $a$: Number of subproblems (e.g., 2 in Merge Sort)
• $b$: Factor by which input is reduced (e.g., 2 in Merge Sort)
• $f(n)$: Time taken to Combine the results (e.g., $O(N)$ in Merge Sort).

Using the theorem, the complexity for Merge Sort and the Max Subarray algorithm above is $O(N \log N)$.