Algo Infinity Verse

01

Introduction

Divide and Conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

When to use it?

Use Divide and Conquer when a problem can be partitioned into independent subproblems, and the combination of the subproblem solutions leads efficiently to the overall solution. It is especially useful for searching, sorting, and geometric problems.

02

The 3-Step Strategy

Every Divide and Conquer algorithm fundamentally consists of three distinct steps:

Divide: Break the given problem into subproblems of same type.
Conquer: Recursively solve these subproblems. If they are small enough, solve them directly (the base case).
Combine: Appropriately combine the answers of the subproblems to form the final answer.

💡

Base Case is Critical: Without a proper base case in your recursion, the "Conquer" step will run infinitely, leading to a Stack Overflow error!

03

Common Applications

Many classic algorithms utilize this paradigm. Here are a few prominent ones:

1. Merge Sort

Divides the array into two halves, recursively sorts them, and then merges the two sorted halves.

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

2. Binary Search

Searches a sorted array by repeatedly dividing the search interval in half. Note that Binary Search is technically a Decrease and Conquer algorithm, but it is often classified under this umbrella.

3. Quick Sort

Picks an element as a pivot and partitions the given array around the picked pivot, before recursively sorting the partitions.

04

Complexity Analysis

The time complexity of a Divide and Conquer algorithm is typically expressed using a recurrence relation and solved using the Master Theorem.

The Master Theorem Formula

For a recurrence of the form: T(n) = aT(n/b) + f(n)

n is the size of the problem.
a is the number of subproblems in the recursion.
n/b is the size of each subproblem.
f(n) is the cost of the work done outside the recursive calls (the divide and combine steps).

For example, in Merge Sort, we divide into 2 subproblems (a=2), each of size n/2 (b=2), and merging takes O(n) time (f(n)=n). Thus: T(n) = 2T(n/2) + O(n), which resolves to O(n log n).

05

Practice Exercises

Test your knowledge with these standard divide and conquer problems!

Majority Element

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times.

We can divide the array into two halves, recursively find the majority element of each half. If the two halves agree, that's the global majority. Otherwise, we count occurrences of both candidates in the current range and return the winner.

cpp

int majorityElement(vector<int>& nums, int l, int r) {
    if (l == r) return nums[l];
    
    int mid = l + (r - l) / 2;
    int leftMajority = majorityElement(nums, l, mid);
    int rightMajority = majorityElement(nums, mid + 1, r);
    
    if (leftMajority == rightMajority) return leftMajority;
    
    int leftCount = count(nums.begin() + l, nums.begin() + r + 1, leftMajority);
    int rightCount = count(nums.begin() + l, nums.begin() + r + 1, rightMajority);
    
    return leftCount > rightCount ? leftMajority : rightMajority;
}

Maximum Subarray

Find the contiguous subarray with the largest sum using a divide and conquer approach.

The max subarray must lie in either the left half, the right half, or crossing the midpoint. We recursively solve for the halves and combine by finding the max crossing sum.

java

public int maxSubArray(int[] nums) {
    return findMax(nums, 0, nums.length - 1);
}

private int findMax(int[] nums, int left, int right) {
    if (left > right) return Integer.MIN_VALUE;
    if (left == right) return nums[left];
    
    int mid = (left + right) / 2;
    int leftMax = findMax(nums, left, mid - 1);
    int rightMax = findMax(nums, mid + 1, right);
    
    int crossMax = maxCrossingSum(nums, left, mid, right);
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

Master the Divide & Conquer Pattern Decompose complex problems into manageable sub-problems

✂️ Learn Divide & Conquer