Skip to main content

Divide and Conquer Pattern

The Divide and Conquer pattern involves breaking down a problem into smaller subproblems, solving them, and then combining the results.

What is Divide and Conquer?​

This algorithmic pattern works by:

  1. Dividing the problem into smaller subproblems
  2. Solving the subproblems recursively
  3. Combining the solutions to create a solution to the original problem

When to Use?​

  • Sorting algorithms (Merge Sort, Quick Sort)
  • Binary Search
  • Finding maximum/minimum in an array
  • Matrix multiplication
  • Closest pair of points

Common Applications​

  • Merge Sort
  • Quick Sort
  • Binary Search
  • Strassen's Matrix Multiplication
  • Karatsuba Algorithm for multiplication

Time Complexity​

The time complexity varies depending on the specific algorithm:

  • Binary Search: O(log n)
  • Merge Sort: O(n log n)
  • Quick Sort: O(n log n) average case

Example Problems​

1. Binary Search Implementation​

Problem Description​

Given a sorted array of integers and a target value, return the index of the target if found, otherwise return -1.

Example​

Input: (arr = [1, 2, 3, 4, 5, 6, 7]), (target = 4);
Output: 3;

Input: (arr = [1, 2, 3, 4, 5, 6, 7]), (target = 9);
Output: -1;

Solution​

function binarySearch(arr, target) {
	let left = 0;
	let right = arr.length - 1;

	while (left <= right) {
		const mid = Math.floor((left + right) / 2);

		if (arr[mid] === target) {
			return mid;
		}

		if (arr[mid] < target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}

	return -1;
}

Time Complexity​

  • Time: O(log n)
  • Space: O(1)

2. Merge Sort Implementation​

Problem Description​

Given an unsorted array of integers, sort the array using the merge sort algorithm.

Example​

Input: [64, 34, 25, 12, 22, 11, 90];
Output: [11, 12, 22, 25, 34, 64, 90];

Solution​

function mergeSort(arr) {
	// Base case
	if (arr.length <= 1) return arr;

	// Divide
	const mid = Math.floor(arr.length / 2);
	const left = arr.slice(0, mid);
	const right = arr.slice(mid);

	// Conquer
	return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
	let result = [];
	let leftIndex = 0;
	let rightIndex = 0;

	// Combine results
	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex++;
		} else {
			result.push(right[rightIndex]);
			rightIndex++;
		}
	}

	// Add remaining elements
	return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Time Complexity​

  • Time: O(n log n)
  • Space: O(n)

Practice Problems​

To master the divide and conquer pattern, try solving these problems:

  1. Quick Sort Implementation
  2. Find Maximum and Minimum in an Array
  3. Count Inversions in an Array
  4. Closest Pair of Points
  5. Strassen's Matrix Multiplication

Common Divide and Conquer Strategies​

  1. Binary Division

    • Divide problem into two equal or almost equal parts
    • Common in searching and sorting algorithms

  2. Multi-way Division

    • Divide problem into more than two parts
    • Used in some advanced algorithms

  3. Unequal Division

    • Divide problem into unequal parts
    • Example: Quick Sort with pivot

Tips for Solving Divide and Conquer Problems​

  1. Identify the base case
  2. Define the divide step clearly
  3. Implement the combine step efficiently
  4. Consider the recursion tree
  5. Analyze space complexity carefully

Additional Resources​