Divide & Conquer

Divide and conquer is not a specific algorithm — it is a problem-solving paradigm. The idea is mechanical: if you can’t solve a big problem directly, cut it in half, solve each half independently, then combine the results. Three steps, every time. The beauty is that “independently” is exactly what recursion gives you for free.

---

1. The Three Steps

Every divide-and-conquer algorithm has the same skeleton:

1. Divide: Split the problem into 2 (or more) smaller subproblems of the same type.

2. Conquer: Solve each subproblem recursively. (Apply the leap of faith: assume it works.)

3. Combine: Merge the results of the subproblems into the solution for the original problem.

The combining step is where most of the real work happens, and where most bugs live. Get the combine step right, and the rest follows.

---

2. Merge Sort

Merge sort is the cleanest example of divide-and-conquer. The key insight: sorting a sorted left half and a sorted right half is O(n) using the two-pointer merge. The hard recursive part is already done for you by assumption.

Derivation

Divide: Split the array at the midpoint into left half and right half.

Conquer: Recursively sort left half. Recursively sort right half. (Leap of faith: they come back sorted.)

Combine: Merge two sorted arrays into one sorted array using two pointers.

void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;               // base case: 0 or 1 element

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);               // conquer left
    mergeSort(arr, mid + 1, right);          // conquer right
    merge(arr, left, mid, right);            // combine
}

void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else                  temp[k++] = arr[j++];
    }
    while (i <= mid)    temp[k++] = arr[i++];
    while (j <= right)  temp[k++] = arr[j++];

    for (int idx = 0; idx < temp.length; idx++)
        arr[left + idx] = temp[idx];
}

Why O(n log n)?

• The divide step creates a recursion tree with log₂(n) levels (you halve n each time until n=1).

• At each level, the merge step does O(n) total work across all calls at that level.

• Total: O(n) work × O(log n) levels = O(n log n).

Properties

• Stable sort: Equal elements maintain their relative order (crucial for sort stability in production code).

• O(n) extra space for the temporary array during merge. This is the price for stability.

• Preferred when stability matters or when sorting linked lists (no random access needed).

What most people get wrong: The merge step. They try to merge in-place without a temp array and make off-by-one errors. Use a temp array. Clarity beats cleverness.

---

3. Quick Sort

Quick sort achieves the same O(n log n) average case but O(1) extra space (in-place). The trade-off: O(n²) worst case on already-sorted input with bad pivot selection.

The Partition Scheme

Lomuto partition (simpler, common in interviews): Choose the last element as pivot. Maintain a boundary i such that all elements ≤ pivot are to the left of i. Scan j from left to right; when arr[j] <= pivot, swap it into the left zone.

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
    return i + 1;  // pivot's final position
}

void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

Hoare partition (original, slightly faster): Use two pointers moving inward from both ends. Harder to implement correctly but makes fewer swaps on average.

Worst Case and How to Avoid It

Worst case O(n²) happens when the pivot is always the minimum or maximum element (e.g., sorted array with last-element pivot). Each partition step reduces the problem by only 1 instead of halving it.

Fix: Randomized pivot. Pick a random index, swap it to the end, then partition. Expected O(n log n) for any input.

void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int rand = low + (int)(Math.random() * (high - low + 1));
    int temp = arr[rand]; arr[rand] = arr[high]; arr[high] = temp;
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

Merge Sort vs. Quick Sort

Property	Merge Sort	Quick Sort
Time (average)	O(n log n)	O(n log n)
Time (worst)	O(n log n)	O(n²) without randomization
Space	O(n)	O(log n) stack
Stable?	Yes	No
Cache performance	Worse (accesses far apart)	Better (good locality)
Preferred for	Linked lists, external sort	Arrays in practice

---

4. Binary Search: The Generalized Template

Binary search is divide-and-conquer applied to a search problem instead of a sort problem. The key invariant: at every step, you maintain the property that the answer (if it exists) lies within [lo, hi].

The Universal Template

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;    // avoid overflow vs (lo+hi)/2

        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;  // not found
}

Invariant being maintained: The answer, if it exists, is in arr[lo..hi]. Each iteration either finds the answer or cuts the search space in half.

Off-by-one is the killer. The most common mistake: hi = mid vs hi = mid - 1, or lo < hi vs lo <= hi. The rule: if you move hi = mid, your loop condition should be lo < hi. If you move hi = mid - 1, use lo <= hi. Be consistent and derive from your invariant.

Applied to Non-Trivial Problems

1. Rotated Sorted Array (LC 33)

Array is sorted but rotated at some pivot. One half is always sorted. Check which half, determine if target is in the sorted half, narrow accordingly.

int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {           // left half is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                               // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

2. Find Peak Element (LC 162)

A peak is any element greater than its neighbors. The key: if nums[mid] < nums[mid+1], a peak must exist in the right half (elements are increasing, so the right side is “uphill”). Otherwise, it must exist in the left half (or at mid).

---

5. The “Search on Answer” Technique

This is the most powerful and least obvious binary search pattern. The setup:

1. The answer you’re looking for is a value in some range [minVal, maxVal].

2. There is a monotone predicate: for all values ≤ answer, the predicate is true (or false); for all values > answer, it flips.

3. You binary search the answer space instead of an array index.

Template:

int lo = minPossibleAnswer, hi = maxPossibleAnswer;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (canAchieve(mid)) hi = mid;   // or lo = mid + 1 depending on direction
    else lo = mid + 1;
}
return lo;

Classic example: Koko Eating Bananas (LC 875)

• Koko eats at speed k bananas/hour. Given pile sizes, find minimum k to finish in h hours.

• Answer range: [1, max(piles)].

• Predicate: canFinish(k, h) — can Koko finish all piles at speed k within h hours? O(n) to check.

• Binary search over k. Total: O(n log(max(piles))).

boolean canFinish(int[] piles, int speed, int h) {
    int hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // ceiling division
    return hours <= h;
}

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Recognition signal: The problem asks for “minimum X such that Y is possible” or “maximum X such that Y is still feasible.” That’s almost always search-on-answer.

---

6. Practice Problems

Sorting:

1. LC 912 — Sort an Array: Implement merge sort. No built-in sort allowed. Acceptance: O(n log n), stable.

2. LC 215 — Kth Largest Element in an Array: Use quickselect (partition-based selection). Derive the O(n) average case.

Binary Search (standard): 3. LC 704 — Binary Search: The template problem. Get the loop termination exactly right. 4. LC 33 — Search in Rotated Sorted Array: Identify which half is sorted, use that to narrow.

Binary Search on Answer Space: 5. LC 875 — Koko Eating Bananas: The canonical search-on-answer problem. Derive the predicate before writing code. 6. LC 1011 — Capacity to Ship Packages Within D Days (Hard): Same pattern as Koko. Answer = minimum ship capacity. Predicate = can we ship all packages in D days at this capacity?

---

Navigation

← Back: 01 — Recursion Mechanics → Next: 03 — Binary Trees ← Phase Overview: README.md