Divide and Conquer Technique

Overview

Divide and Conquer is an algorithmic paradigm that breaks down a problem into smaller subproblems, solves them, and then combines these solutions to create a solution to the original problem.

Three Main Steps

1. Divide: Break the problem into smaller subproblems
2. Conquer: Recursively solve the subproblems
3. Combine: Combine the solutions of subproblems to create a solution to the original problem

Common Examples and Implementations

1. Merge Sort

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
    const sortedLeft = mergeSort(left);
    const sortedRight = mergeSort(right);
    
    // Combine
    return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// Usage
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// Output: [3, 9, 10, 27, 38, 43, 82]

2. Binary Search

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
    // Base case
    if (left > right) return -1;
    
    // Divide
    const mid = Math.floor((left + right) / 2);
    
    // Conquer
    if (arr[mid] === target) return mid;
    
    if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

// Usage
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7], 5));
// Output: 4

3. Maximum Subarray Sum

function maxSubarray(arr, left = 0, right = arr.length - 1) {
    // Base case
    if (left === right) return arr[left];
    
    // Divide
    const mid = Math.floor((left + right) / 2);
    
    // Conquer
    const leftSum = maxSubarray(arr, left, mid);
    const rightSum = maxSubarray(arr, mid + 1, right);
    const crossSum = maxCrossingSum(arr, left, mid, right);
    
    // Combine
    return Math.max(leftSum, rightSum, crossSum);
}

function maxCrossingSum(arr, left, mid, right) {
    let sum = 0;
    let leftSum = -Infinity;
    let rightSum = -Infinity;
    
    // Find maximum sum for left half
    for (let i = mid; i >= left; i--) {
        sum += arr[i];
        leftSum = Math.max(leftSum, sum);
    }
    
    // Find maximum sum for right half
    sum = 0;
    for (let i = mid + 1; i <= right; i++) {
        sum += arr[i];
        rightSum = Math.max(rightSum, sum);
    }
    
    return leftSum + rightSum;
}

// Usage
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// Output: 6 (subarray [4, -1, 2, 1])

4. Quick Sort

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        // Divide
        const pivotIndex = partition(arr, left, right);
        
        // Conquer
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left - 1;
    
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

// Usage
console.log(quickSort([64, 34, 25, 12, 22, 11, 90]));
// Output: [11, 12, 22, 25, 34, 64, 90]

Time Complexity Analysis

Algorithm	Average Case	Worst Case	Space Complexity
Merge Sort	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n²)	O(log n)
Binary Search	O(log n)	O(log n)	O(1)
Maximum Subarray	O(n log n)	O(n log n)	O(log n)

When to Use Divide and Conquer

Good Use Cases:

1. Sorting large datasets
2. Searching in sorted arrays
3. Matrix multiplication
4. Finding closest pair of points
5. Computing Fibonacci numbers
6. Finding maximum/minimum

Advantages:

• Solves complex problems by breaking them down
• Often leads to efficient solutions
• Parallelization potential
• Reusable solutions for similar problems

Disadvantages:

• Recursive nature can use more space
• May be overkill for simple problems
• Overhead in dividing and combining steps

Implementation Template

function divideAndConquer(problem) {
    // Base case
    if (problem is small enough) {
        return solve(problem);
    }
    
    // Divide
    subproblems = divide(problem);
    
    // Conquer
    subSolutions = subproblems.map(subproblem => 
        divideAndConquer(subproblem)
    );
    
    // Combine
    return combine(subSolutions);
}

Count Inversions in an array

/**
 * Problem: Count Inversions in an array
 * An inversion occurs when a[i] > a[j] where i < j
 * Uses divide and conquer approach similar to merge sort
 */
function countInversions(arr) {
    // Base case
    if (arr.length <= 1) return { 
        sortedArr: arr, 
        count: 0 
    };
    
    // Divide
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    
    // Conquer
    const leftResult = countInversions(left);
    const rightResult = countInversions(right);
    
    // Combine
    return mergeAndCount(leftResult.sortedArr, rightResult.sortedArr, 
                        leftResult.count + rightResult.count);
}

function mergeAndCount(left, right, count) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            // Inversion found: all elements from i to left.length are inversions
            count += left.length - i;
            result.push(right[j++]);
        }
    }
    
    return {
        sortedArr: result.concat(left.slice(i)).concat(right.slice(j)),
        count: count
    };
}

// Example usage
const arr = [8, 4, 2, 1];
console.log(countInversions(arr));
// Output: { sortedArr: [1, 2, 4, 8], count: 6 }
// Inversions are: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1)