Divide and Conquer

1. Merge Sort Pattern Application

Phase	Operation	Complexity	Key Insight
Divide	Split array into two halves	`O(1)`	Find middle index
Conquer	Recursively sort both halves	`T(n/2) + T(n/2)`	Two subproblems of size n/2
Combine	Merge two sorted arrays	`O(n)`	Linear scan with two pointers
Total Time	Master theorem analysis	`O(n log n)`	log n levels, O(n) work per level

Example: Merge sort implementation

function mergeSort(arr) {
    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]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    
    // Add remaining elements
    while (i < left.length) {
        result.push(left[i]);
        i++;
    }
    
    while (j < right.length) {
        result.push(right[j]);
        j++;
    }
    
    return result;
}

// [38,27,43,3,9,82,10] -> [3,9,10,27,38,43,82]
// Time: O(n log n), Space: O(n)

Example: Count inversions using merge sort

function countInversions(arr) {
    if (arr.length <= 1) return { sorted: arr, count: 0 };
    
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    
    const leftResult = countInversions(left);
    const rightResult = countInversions(right);
    
    const merged = mergeAndCount(leftResult.sorted, rightResult.sorted);
    
    return {
        sorted: merged.sorted,
        count: leftResult.count + rightResult.count + merged.count
    };
}

function mergeAndCount(left, right) {
    const result = [];
    let i = 0, j = 0, count = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
            // All remaining elements in left are inversions
            count += left.length - i;
        }
    }
    
    while (i < left.length) result.push(left[i++]);
    while (j < right.length) result.push(right[j++]);
    
    return { sorted: result, count };
}

// [2,4,1,3,5] -> 3 inversions: (2,1), (4,1), (4,3)
// Application: Measure of "sortedness"

2. Quick Sort Partition Strategy

Partition Scheme	Strategy	Swaps	Characteristics
Lomuto Partition	Single pointer, swap smaller elements to front	More swaps	Simpler, easier to understand
Hoare Partition	Two pointers from both ends	Fewer swaps	More efficient, trickier to implement
3-way Partition	Three regions: <pivot, =pivot, >pivot	Optimal for duplicates	Handles many equal elements well
Average Case	Random pivot selection	`O(n log n)`	Expected performance

Example: Quick sort with Lomuto partition

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

function lomutoPartition(arr, left, right) {
    const pivot = arr[right]; // Choose last as pivot
    let i = left;
    
    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}

// Time: O(n log n) average, O(n²) worst
// Space: O(log n) recursion stack

Example: Quick sort with Hoare partition

function quickSortHoare(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        const pivotIndex = hoarePartition(arr, left, right);
        quickSortHoare(arr, left, pivotIndex);
        quickSortHoare(arr, pivotIndex + 1, right);
    }
    return arr;
}

function hoarePartition(arr, left, right) {
    const pivot = arr[Math.floor((left + right) / 2)];
    let i = left - 1;
    let j = right + 1;
    
    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);
        
        do {
            j--;
        } while (arr[j] > pivot);
        
        if (i >= j) return j;
        
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

// Fewer swaps than Lomuto

Example: 3-way partition (Dutch National Flag)

function quickSort3Way(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr;
    
    const pivot = arr[left];
    let lt = left;      // Elements < pivot
    let i = left + 1;   // Current element
    let gt = right;     // Elements > pivot
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            [arr[lt], arr[i]] = [arr[i], arr[lt]];
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            [arr[i], arr[gt]] = [arr[gt], arr[i]];
            gt--;
        } else {
            i++;
        }
    }
    
    quickSort3Way(arr, left, lt - 1);
    quickSort3Way(arr, gt + 1, right);
    
    return arr;
}

// [3,5,3,2,3,1,3,4,3] -> sorted efficiently
// Optimal when many duplicates exist
// Equal elements not recursed on

3. Binary Tree Divide Conquer

Pattern	Approach	Combine Step	Example Problem
Height/Depth	Recurse on children, return max + 1	`max(left, right) + 1`	Tree height, depth calculation
Path Sum	Recurse with remaining sum	Check if current + child paths work	Path sum, binary tree paths
Diameter	Track max path through each node	Max of left+right or child diameters	Longest path in tree
Balanced Check	Return height and balance status	Check \|left.height - right.height\| <= 1	Validate balanced tree

Example: Tree height/depth

function maxDepth(root) {
    // Base case
    if (!root) return 0;
    
    // Divide: recurse on children
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    // Conquer: combine results
    return Math.max(leftDepth, rightDepth) + 1;
}

// Tree with 3 levels -> depth = 3
// Time: O(n), Space: O(h) where h = height

Example: Balanced binary tree

function isBalanced(root) {
    function checkHeight(node) {
        if (!node) return 0;
        
        const leftHeight = checkHeight(node.left);
        if (leftHeight === -1) return -1;
        
        const rightHeight = checkHeight(node.right);
        if (rightHeight === -1) return -1;
        
        // Check balance condition
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // Not balanced
        }
        
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    return checkHeight(root) !== -1;
}

// Returns true if balanced, false otherwise

Example: Binary tree diameter

function diameterOfBinaryTree(root) {
    let maxDiameter = 0;
    
    function height(node) {
        if (!node) return 0;
        
        const leftHeight = height(node.left);
        const rightHeight = height(node.right);
        
        // Update diameter: path through current node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        
        // Return height for parent
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    height(root);
    return maxDiameter;
}

//       1
//      / \
//     2   3
//    / \
//   4   5
// Diameter = 3 (4-2-1-3 or 5-2-1-3)
// Time: O(n), Space: O(h)

Example: Lowest common ancestor (LCA)

function lowestCommonAncestor(root, p, q) {
    // Base case
    if (!root || root === p || root === q) {
        return root;
    }
    
    // Divide: search in subtrees
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    // Conquer: combine results
    if (left && right) {
        // p and q on different sides
        return root;
    }
    
    // Both on same side or one not found
    return left || right;
}

// Finds the lowest node that has both p and q as descendants
// Time: O(n), Space: O(h)

4. Closest Pair of Points

Step	Operation	Complexity	Purpose
Preprocessing	Sort points by x-coordinate	`O(n log n)`	Enable divide step
Divide	Split into left/right halves	`O(1)`	Find middle x-coordinate
Conquer	Find closest in each half recursively	`T(n/2)`	Solve subproblems
Combine	Check strip around midline	`O(n)`	Find cross-boundary pairs

Example: Closest pair of points

function closestPair(points) {
    // Sort by x-coordinate
    points.sort((a, b) => a.x - b.x);
    
    function distance(p1, p2) {
        const dx = p1.x - p2.x;
        const dy = p1.y - p2.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    function bruteForce(pts) {
        let minDist = Infinity;
        for (let i = 0; i < pts.length; i++) {
            for (let j = i + 1; j < pts.length; j++) {
                minDist = Math.min(minDist, distance(pts[i], pts[j]));
            }
        }
        return minDist;
    }
    
    function closestUtil(pts) {
        const n = pts.length;
        
        // Base case: brute force for small n
        if (n <= 3) return bruteForce(pts);
        
        // Divide
        const mid = Math.floor(n / 2);
        const midPoint = pts[mid];
        const left = pts.slice(0, mid);
        const right = pts.slice(mid);
        
        // Conquer
        const dl = closestUtil(left);
        const dr = closestUtil(right);
        const d = Math.min(dl, dr);
        
        // Combine: check strip
        const strip = pts.filter(p => Math.abs(p.x - midPoint.x) < d);
        
        // Sort strip by y-coordinate
        strip.sort((a, b) => a.y - b.y);
        
        let minDist = d;
        for (let i = 0; i < strip.length; i++) {
            // Only check next 7 points (proven upper bound)
            for (let j = i + 1; j < strip.length && 
                 (strip[j].y - strip[i].y) < minDist; j++) {
                minDist = Math.min(minDist, distance(strip[i], strip[j]));
            }
        }
        
        return minDist;
    }
    
    return closestUtil(points);
}

// Points: [{x:2,y:3}, {x:12,y:30}, {x:40,y:50}, {x:5,y:1}]
// Returns minimum distance between any two points
// Time: O(n log² n), can be optimized to O(n log n)

5. Maximum Subarray Divide Conquer

Case	Location	Computation	Complexity
Left Half	Entirely in left subarray	Recursive call on left	`T(n/2)`
Right Half	Entirely in right subarray	Recursive call on right	`T(n/2)`
Crossing Middle	Spans across midpoint	Find max from mid to left + mid to right	`O(n)`
Total	Max of all three cases	`max(left, right, cross)`	`O(n log n)`

Example: Maximum subarray divide and conquer

function maxSubArrayDC(nums) {
    function maxCrossingSum(nums, left, mid, right) {
        // Left side of mid
        let leftSum = -Infinity;
        let sum = 0;
        for (let i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }
        
        // Right side of mid
        let rightSum = -Infinity;
        sum = 0;
        for (let i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }
        
        return leftSum + rightSum;
    }
    
    function maxSubArrayHelper(nums, left, right) {
        // Base case: single element
        if (left === right) return nums[left];
        
        const mid = Math.floor((left + right) / 2);
        
        // Divide
        const leftMax = maxSubArrayHelper(nums, left, mid);
        const rightMax = maxSubArrayHelper(nums, mid + 1, right);
        const crossMax = maxCrossingSum(nums, left, mid, right);
        
        // Conquer
        return Math.max(leftMax, rightMax, crossMax);
    }
    
    return maxSubArrayHelper(nums, 0, nums.length - 1);
}

// [-2,1,-3,4,-1,2,1,-5,4] -> 6 (subarray [4,-1,2,1])
// Time: O(n log n), Space: O(log n)
// Note: Kadane's algorithm is O(n), but this demonstrates D&C

6. Karatsuba Multiplication

Step	Formula	Multiplications	Insight
Standard Multiplication	Split into halves, 4 recursive mults	4	T(n) = 4T(n/2) + O(n) = O(n²)
Karatsuba Trick	Use (a+b)(c+d) to eliminate one mult	3	T(n) = 3T(n/2) + O(n) = O(n^1.58)
Key Formula	`ac×10^n + ((a+b)(c+d) - ac - bd)×10^(n/2) + bd`	3: ac, bd, (a+b)(c+d)	Trade multiplications for additions
Application	Large integer multiplication	Asymptotically faster	Used in cryptography, bignum libraries

Example: Karatsuba multiplication

function karatsuba(x, y) {
    // Base case: small numbers
    if (x < 10 || y < 10) {
        return x * y;
    }
    
    // Find the size of the numbers
    const n = Math.max(x.toString().length, y.toString().length);
    const half = Math.floor(n / 2);
    const divisor = Math.pow(10, half);
    
    // Split x and y
    const a = Math.floor(x / divisor);  // High part of x
    const b = x % divisor;               // Low part of x
    const c = Math.floor(y / divisor);  // High part of y
    const d = y % divisor;               // Low part of y
    
    // Three recursive multiplications (Karatsuba's trick)
    const ac = karatsuba(a, c);
    const bd = karatsuba(b, d);
    const ad_plus_bc = karatsuba(a + b, c + d) - ac - bd;
    
    // Combine results
    // x*y = ac*10^n + (ad+bc)*10^(n/2) + bd
    return ac * Math.pow(10, 2 * half) + 
           ad_plus_bc * Math.pow(10, half) + 
           bd;
}

// 1234 * 5678
// Standard: 4 multiplications at each level
// Karatsuba: 3 multiplications at each level
// Result: 7006652
// Time: O(n^log₂3) ≈ O(n^1.585) vs O(n²)

Example: String-based Karatsuba for very large numbers

function karatsubaString(x, y) {
    // Remove leading zeros
    x = x.replace(/^0+/, '') || '0';
    y = y.replace(/^0+/, '') || '0';
    
    // Base case
    if (x.length === 1 || y.length === 1) {
        return (parseInt(x) * parseInt(y)).toString();
    }
    
    // Pad to same length
    const n = Math.max(x.length, y.length);
    x = x.padStart(n, '0');
    y = y.padStart(n, '0');
    
    const half = Math.floor(n / 2);
    
    // Split
    const a = x.slice(0, n - half);
    const b = x.slice(n - half);
    const c = y.slice(0, n - half);
    const d = y.slice(n - half);
    
    // Helper to add large numbers as strings
    function addStrings(num1, num2) {
        let result = '';
        let carry = 0;
        let i = num1.length - 1;
        let j = num2.length - 1;
        
        while (i >= 0 || j >= 0 || carry) {
            const digit1 = i >= 0 ? parseInt(num1[i]) : 0;
            const digit2 = j >= 0 ? parseInt(num2[j]) : 0;
            const sum = digit1 + digit2 + carry;
            result = (sum % 10) + result;
            carry = Math.floor(sum / 10);
            i--;
            j--;
        }
        
        return result;
    }
    
    // Helper to subtract large numbers
    function subtractStrings(num1, num2) {
        // Simplified: assumes num1 >= num2
        let result = '';
        let borrow = 0;
        let i = num1.length - 1;
        let j = num2.length - 1;
        
        while (i >= 0) {
            let digit1 = parseInt(num1[i]);
            const digit2 = j >= 0 ? parseInt(num2[j]) : 0;
            digit1 -= borrow;
            
            if (digit1 < digit2) {
                digit1 += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            
            result = (digit1 - digit2) + result;
            i--;
            j--;
        }
        
        return result.replace(/^0+/, '') || '0';
    }
    
    // Three multiplications
    const ac = karatsubaString(a, c);
    const bd = karatsubaString(b, d);
    const abcd = karatsubaString(addStrings(a, b), addStrings(c, d));
    const middle = subtractStrings(subtractStrings(abcd, ac), bd);
    
    // Combine with powers of 10 (append zeros)
    return addStrings(
        addStrings(ac + '0'.repeat(2 * half), middle + '0'.repeat(half)),
        bd
    );
}

// Can multiply arbitrarily large integers
// "12345678901234567890" * "98765432109876543210"

Divide and Conquer Summary

Core Pattern: Divide → Conquer → Combine
Merge Sort: O(n log n), stable, predictable performance
Quick Sort: O(n log n) average, O(n²) worst, in-place
Binary Tree: Natural recursion on left/right subtrees
Closest Pair: Geometric divide and conquer, O(n log n)
Max Subarray: Consider left, right, and crossing cases
Karatsuba: Reduce multiplications from 4 to 3, O(n^1.58)

Note: Divide and conquer achieves O(n log n) for many problems by breaking into smaller subproblems. Master theorem: T(n) = aT(n/b) + f(n). For merge sort: a=2, b=2, f(n)=O(n) → O(n log n). For Karatsuba: a=3, b=2 → O(n^log₂3) ≈ O(n^1.585).

Warning: Divide and conquer has recursion overhead - for small inputs, simple iterative solutions may be faster. Quick sort's O(n²) worst case occurs with poor pivot selection (already sorted array with first/last pivot). Use random pivot or median-of-3 for better performance. Merge sort requires O(n) extra space.

Related Cheatsheets

Datastructures-algorithms