Divide and Conquer Algorithms

Divide and conquer is a fundamental algorithmic paradigm that solves problems by breaking them into smaller subproblems, solving them recursively, and combining the results. This approach leads to elegant solutions with optimal time complexities for many classic problems.

Merge Sort - Classic Divide and Conquer

Merge sort exemplifies the divide-and-conquer approach: divide the array into halves, recursively sort each half, then merge the sorted halves.

Merge Sort Implementation

#include <iostream>
#include <vector>
using namespace std;

class MergeSort {
public:
    void mergeSort(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        
        // Divide: recursively sort both halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Conquer: merge the sorted halves
        merge(arr, left, mid, right);
    }
    
private:
    void merge(vector<int>& arr, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        
        // Merge two sorted arrays
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        // Copy remaining elements
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        
        // Copy back to original array
        for (int i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
};

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
    
    cout << "Original array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    MergeSort ms;
    ms.mergeSort(arr, 0, arr.size() - 1);
    
    cout << "Sorted array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    return 0;
}

Merge sort has O(n log n) time complexity and O(n) space complexity. It is a stable sorting algorithm and particularly useful for sorting linked lists.

Quick Sort and Quick Select

Quick sort partitions the array around a pivot element, then recursively sorts the partitions. Quick select finds the kth smallest element efficiently.

Quick Sort and Quick Select

#include <iostream>
#include <vector>
#include <random>
using namespace std;

class QuickSort {
public:
    void quickSort(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        
        // Randomize pivot to avoid worst case
        int randomIndex = left + rand() % (right - left + 1);
        swap(arr[left], arr[randomIndex]);
        
        int pivotIndex = partition(arr, left, right);
        
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    
    // Quick Select - find kth smallest element
    int quickSelect(vector<int>& arr, int left, int right, int k) {
        if (left == right) return arr[left];
        
        int randomIndex = left + rand() % (right - left + 1);
        swap(arr[left], arr[randomIndex]);
        
        int pivotIndex = partition(arr, left, right);
        
        if (pivotIndex == k) return arr[pivotIndex];
        else if (pivotIndex > k) return quickSelect(arr, left, pivotIndex - 1, k);
        else return quickSelect(arr, pivotIndex + 1, right, k);
    }
    
private:
    int partition(vector<int>& arr, int left, int right) {
        int pivot = arr[left];
        int i = left, j = right;
        
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] <= pivot) i++;
            if (i < j) arr[j--] = arr[i];
        }
        
        arr[i] = pivot;
        return i;
    }
};

int main() {
    srand(time(nullptr));
    
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
    
    cout << "Original array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    QuickSort qs;
    vector<int> sortArr = arr;
    qs.quickSort(sortArr, 0, sortArr.size() - 1);
    
    cout << "Sorted array: ";
    for (int x : sortArr) cout << x << " ";
    cout << endl;
    
    // Test quick select
    int k = 5; // 6th smallest element (0-indexed)
    int kthSmallest = qs.quickSelect(arr, 0, arr.size() - 1, k);
    cout << "The " << (k + 1) << "th smallest element: " << kthSmallest << endl;
    
    return 0;
}

Quick sort has O(n log n) average time complexity, O(n²) worst case. Quick select can find the kth smallest element in O(n) average time.

Maximum Subarray Problem

The maximum subarray problem can be solved elegantly using divide and conquer, achieving O(n log n) complexity.

Maximum Subarray - Divide and Conquer

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class MaxSubarray {
public:
    struct Result {
        int maxSum;
        int left;
        int right;
        
        Result(int sum = INT_MIN, int l = -1, int r = -1) 
            : maxSum(sum), left(l), right(r) {}
    };
    
    Result maxSubarrayDC(vector<int>& arr, int left, int right) {
        // Base case: single element
        if (left == right) {
            return Result(arr[left], left, right);
        }
        
        int mid = left + (right - left) / 2;
        
        // Recursively find max subarray in left and right halves
        Result leftResult = maxSubarrayDC(arr, left, mid);
        Result rightResult = maxSubarrayDC(arr, mid + 1, right);
        
        // Find max subarray crossing the middle
        Result crossResult = maxCrossingSubarray(arr, left, mid, right);
        
        // Return the maximum of three cases
        if (leftResult.maxSum >= rightResult.maxSum && 
            leftResult.maxSum >= crossResult.maxSum) {
            return leftResult;
        } else if (rightResult.maxSum >= leftResult.maxSum && 
                   rightResult.maxSum >= crossResult.maxSum) {
            return rightResult;
        } else {
            return crossResult;
        }
    }
    
private:
    Result maxCrossingSubarray(vector<int>& arr, int left, int mid, int right) {
        // Find max sum extending left from mid
        int leftSum = INT_MIN;
        int sum = 0;
        int maxLeft = mid;
        
        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        
        // Find max sum extending right from mid+1
        int rightSum = INT_MIN;
        sum = 0;
        int maxRight = mid + 1;
        
        for (int i = mid + 1; i <= right; i++) {
            sum += arr[i];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = i;
            }
        }
        
        return Result(leftSum + rightSum, maxLeft, maxRight);
    }
};

// Kadane's algorithm for comparison (O(n))
int kadane(vector<int>& arr) {
    int maxSoFar = arr[0];
    int maxEndingHere = arr[0];
    
    for (int i = 1; i < arr.size(); i++) {
        maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

int main() {
    vector<int> arr = {-2, -3, 4, -1, -2, 1, 5, -3};
    
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    MaxSubarray ms;
    MaxSubarray::Result result = ms.maxSubarrayDC(arr, 0, arr.size() - 1);
    
    cout << "Divide & Conquer - Max sum: " << result.maxSum << endl;
    cout << "Subarray indices: [" << result.left << ", " << result.right << "]" << endl;
    cout << "Subarray: ";
    for (int i = result.left; i <= result.right; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    cout << "Kadane's algorithm: " << kadane(arr) << endl;
    
    return 0;
}

The divide-and-conquer approach considers three cases: max subarray in left half, right half, or crossing the middle. Time complexity is O(n log n).

Closest Pair of Points

Finding the closest pair of points in 2D plane using divide and conquer achieves O(n log n) complexity, better than the brute force O(n²) approach.

Closest Pair of Points

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <float.h>
using namespace std;

struct Point {
    double x, y;
    
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    double distanceTo(const Point& other) const {
        return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
    }
};

class ClosestPair {
public:
    double findClosestPair(vector<Point>& points) {
        // Sort points by x-coordinate
        sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
            return a.x < b.x;
        });
        
        return closestPairRec(points, 0, points.size() - 1);
    }
    
private:
    double closestPairRec(vector<Point>& points, int left, int right) {
        int n = right - left + 1;
        
        // Base case: brute force for small arrays
        if (n <= 3) {
            return bruteForce(points, left, right);
        }
        
        int mid = left + (right - left) / 2;
        Point midPoint = points[mid];
        
        // Recursively find closest pairs in left and right halves
        double leftMin = closestPairRec(points, left, mid);
        double rightMin = closestPairRec(points, mid + 1, right);
        
        double minDist = min(leftMin, rightMin);
        
        // Find points close to the dividing line
        vector<Point> strip;
        for (int i = left; i <= right; i++) {
            if (abs(points[i].x - midPoint.x) < minDist) {
                strip.push_back(points[i]);
            }
        }
        
        // Sort strip by y-coordinate
        sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) {
            return a.y < b.y;
        });
        
        // Find closest points in strip
        return min(minDist, stripClosest(strip, minDist));
    }
    
    double bruteForce(vector<Point>& points, int left, int right) {
        double minDist = DBL_MAX;
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                minDist = min(minDist, points[i].distanceTo(points[j]));
            }
        }
        return minDist;
    }
    
    double stripClosest(vector<Point>& strip, double minDist) {
        double min_val = minDist;
        
        for (int i = 0; i < strip.size(); i++) {
            // Check at most 7 points (proven geometrically)
            for (int j = i + 1; j < strip.size() && 
                 (strip[j].y - strip[i].y) < min_val; j++) {
                min_val = min(min_val, strip[i].distanceTo(strip[j]));
            }
        }
        
        return min_val;
    }
};

int main() {
    vector<Point> points = {
        Point(2, 3), Point(12, 30), Point(40, 50), Point(5, 1),
        Point(12, 10), Point(3, 4), Point(1, 1), Point(8, 7)
    };
    
    cout << "Points:" << endl;
    for (int i = 0; i < points.size(); i++) {
        cout << "(" << points[i].x << ", " << points[i].y << ")" << endl;
    }
    
    ClosestPair cp;
    double closestDistance = cp.findClosestPair(points);
    
    cout << "Closest pair distance: " << closestDistance << endl;
    
    return 0;
}

The algorithm divides points by x-coordinate, finds closest pairs in each half, then checks points near the dividing line. The key insight is that we only need to check at most 7 points in the strip.

Key Takeaways

Divide and conquer breaks problems into smaller subproblems, solves them recursively, and combines results
Time complexity often follows the recurrence T(n) = aT(n/b) + f(n), analyzed using Master Theorem
Common applications: sorting algorithms, closest pair, maximum subarray, fast multiplication
Often provides optimal solutions with elegant recursive structure