Skip to main content
Back to Library
cracking the tech interview system design and algorithms in java 25

Divide and Conquer

10 min read Chapter 66 of 75
Summary

Covers the three-step divide-conquer-combine framework, Master Theorem for...

Covers the three-step divide-conquer-combine framework, Master Theorem for recurrence solving, and applications including merge sort, quicksort, closest pair of points, and Strassen's matrix multiplication.

Divide and Conquer

Divide and conquer is the most intuitive algorithm paradigm. You take a problem, split it into smaller pieces of the same type, solve each piece, and combine the results. The concept is ancient — military generals, corporate managers, and software engineers all rely on the same principle: large problems become manageable when you break them down.

What makes divide and conquer algorithmic rather than platitude is the precise three-step structure and the mathematical machinery (the Master Theorem) for analyzing the resulting recurrences.

The Three-Step Framework

Every divide and conquer algorithm follows three steps:

1. Divide

Break the problem into smaller subproblems — usually two halves, but sometimes more. The subproblems must be the same type as the original, differing only in size.

2. Conquer

Solve each subproblem recursively. When the subproblem is small enough (the base case), solve it directly without further recursion.

3. Combine

Merge the subproblem solutions into a solution for the original problem. This is often where the real work happens — and where the algorithm’s efficiency is determined.

The elegance of D&C lies in trust: you trust that the recursive calls produce correct results for smaller inputs, then you focus on how to combine those results. This is the same “trust the recursion” principle that governs all recursive thinking.

The Master Theorem

Most D&C algorithms produce a recurrence of the form:

$$T(n) = a \cdot T!\left(\frac{n}{b}\right) + O(n^d)$$

where:

  • a = number of subproblems
  • b = factor by which the problem shrinks
  • d = exponent of the work done outside the recursive calls (the divide + combine cost)

The Master Theorem solves this recurrence in three cases by comparing $d$ with $\log_b a$:

Case 1: $d < \log_b a$ The recursive work dominates. The tree has more work at the leaves. $$T(n) = O(n^{\log_b a})$$

Case 2: $d = \log_b a$ The work is evenly spread across all levels. $$T(n) = O(n^d \log n)$$

Case 3: $d > \log_b a$ The combine work dominates. The root level does the most work. $$T(n) = O(n^d)$$

Worked Examples

Merge Sort: $T(n) = 2T(n/2) + O(n)$

  • $a = 2$, $b = 2$, $d = 1$
  • $\log_b a = \log_2 2 = 1 = d$ → Case 2
  • $T(n) = O(n \log n)$ ✓

Binary Search: $T(n) = T(n/2) + O(1)$

  • $a = 1$, $b = 2$, $d = 0$
  • $\log_b a = \log_2 1 = 0 = d$ → Case 2
  • $T(n) = O(\log n)$ ✓

Strassen’s Matrix Multiplication: $T(n) = 7T(n/2) + O(n^2)$

  • $a = 7$, $b = 2$, $d = 2$
  • $\log_b a = \log_2 7 \approx 2.81 > 2 = d$ → Case 1
  • $T(n) = O(n^{\log_2 7}) \approx O(n^{2.81})$, beating the naïve $O(n^3)$

Karatsuba Multiplication: $T(n) = 3T(n/2) + O(n)$

  • $a = 3$, $b = 2$, $d = 1$
  • $\log_b a = \log_2 3 \approx 1.58 > 1 = d$ → Case 1
  • $T(n) = O(n^{1.58})$, beating the naïve $O(n^2)$ for large integer multiplication

The Master Theorem is a powerful shortcut. Memorize the three cases and you can analyze any D&C recurrence in seconds during an interview.

Classic D&C Problems

Maximum Subarray Sum (D&C Approach)

Find the contiguous subarray with the largest sum. The D&C approach divides the array at its midpoint, then the maximum subarray either lies entirely in the left half, entirely in the right half, or crosses the midpoint.

int maxSubArrayDC(int[] nums) {
    return maxSub(nums, 0, nums.length - 1);
}

int maxSub(int[] nums, int left, int right) {
    if (left == right) return nums[left];

    int mid = left + (right - left) / 2;
    int leftMax = maxSub(nums, left, mid);
    int rightMax = maxSub(nums, mid + 1, right);
    int crossMax = maxCrossing(nums, left, mid, right);

    return Math.max(leftMax, Math.max(rightMax, crossMax));
}

int maxCrossing(int[] nums, int left, int mid, int right) {
    int leftSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    return leftSum + rightSum;
}

Analysis: $T(n) = 2T(n/2) + O(n) = O(n \log n)$ by Case 2 of the Master Theorem.

Note that Kadane’s algorithm solves this in $O(n)$ with a single pass. The D&C approach is instructive for understanding the paradigm, but it is not the optimal solution for this specific problem. In an interview, mention both approaches and explain why Kadane’s wins here.

Power Function: $x^n$ in $O(\log n)$

Computing $x^n$ naively requires $n$ multiplications. D&C cuts this to $O(\log n)$ by squaring:

$$x^n = \begin{cases} (x^{n/2})^2 & \text{if } n \text{ is even} \ x \cdot x^{n-1} & \text{if } n \text{ is odd} \end{cases}$$

double power(double x, long n) {
    if (n < 0) {
        x = 1.0 / x;
        n = -n;
    }
    return fastPow(x, n);
}

double fastPow(double x, long n) {
    if (n == 0) return 1.0;
    double half = fastPow(x, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

Analysis: $T(n) = T(n/2) + O(1) = O(\log n)$. Each recursive call halves the exponent, and a single multiplication is performed at each level.

Closest Pair of Points

Given $n$ points in 2D space, find the two points with the smallest Euclidean distance. A brute-force check of all pairs runs in $O(n^2)$. D&C achieves $O(n \log n)$.

Algorithm:

  1. Sort points by x-coordinate.
  2. Divide: split at the median x-coordinate into left and right halves.
  3. Conquer: recursively find the closest pair in each half. Let $\delta = \min(\delta_L, \delta_R)$.
  4. Combine: check points within a vertical strip of width $2\delta$ centered on the dividing line. For each point in the strip, compare it only to points within $\delta$ in the y-direction — this bounds comparisons to at most 6 per point (a geometric argument).
record Point(double x, double y) {}

double closestPair(Point[] points) {
    Point[] sortedByX = points.clone();
    Arrays.sort(sortedByX, Comparator.comparingDouble(Point::x));
    return closestRec(sortedByX, 0, sortedByX.length - 1);
}

double closestRec(Point[] pts, int left, int right) {
    if (right - left < 3) {
        return bruteForce(pts, left, right);
    }

    int mid = left + (right - left) / 2;
    double midX = pts[mid].x();

    double deltaLeft = closestRec(pts, left, mid);
    double deltaRight = closestRec(pts, mid + 1, right);
    double delta = Math.min(deltaLeft, deltaRight);

    // Build strip of points within delta of the dividing line
    List<Point> strip = new ArrayList<>();
    for (int i = left; i <= right; i++) {
        if (Math.abs(pts[i].x() - midX) < delta) {
            strip.add(pts[i]);
        }
    }
    strip.sort(Comparator.comparingDouble(Point::y));

    // Check strip — at most 6 comparisons per point
    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size()
                && (strip.get(j).y() - strip.get(i).y()) < delta; j++) {
            delta = Math.min(delta, distance(strip.get(i), strip.get(j)));
        }
    }

    return delta;
}

double distance(Point a, Point b) {
    double dx = a.x() - b.x();
    double dy = a.y() - b.y();
    return Math.sqrt(dx * dx + dy * dy);
}

double bruteForce(Point[] pts, int left, int right) {
    double minDist = Double.MAX_VALUE;
    for (int i = left; i <= right; i++) {
        for (int j = i + 1; j <= right; j++) {
            minDist = Math.min(minDist, distance(pts[i], pts[j]));
        }
    }
    return minDist;
}

Analysis: The recurrence is $T(n) = 2T(n/2) + O(n \log n)$ if we sort the strip at each level (which gives $O(n \log^2 n)$ total). With a merge-sort-style y-sort propagated through the recursion, the strip merge becomes $O(n)$, yielding $T(n) = 2T(n/2) + O(n) = O(n \log n)$.

The key insight is that the strip check is $O(n)$ despite appearing quadratic: the $\delta$ constraint limits each point to at most 6 neighbors, a result of packing geometry in a $\delta \times 2\delta$ rectangle.

Count Inversions (Merge Sort Modification)

An inversion is a pair $(i, j)$ where $i < j$ but $a[i] > a[j]$. Counting inversions measures how “unsorted” an array is. Brute force is $O(n^2)$; merge sort counts inversions during the merge step in $O(n \log n)$.

long countInversions(int[] arr) {
    int[] temp = new int[arr.length];
    return mergeSort(arr, temp, 0, arr.length - 1);
}

long mergeSort(int[] arr, int[] temp, int left, int right) {
    if (left >= right) return 0;

    int mid = left + (right - left) / 2;
    long count = 0;
    count += mergeSort(arr, temp, left, mid);
    count += mergeSort(arr, temp, mid + 1, right);
    count += merge(arr, temp, left, mid, right);
    return count;
}

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

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // arr[i] > arr[j]: all remaining elements in left half
            // (from i to mid) form inversions with arr[j]
            inversions += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, left, arr, left, right - left + 1);
    return inversions;
}

The trick: when arr[j] is chosen before arr[i] during the merge, every remaining element in the left half (from i to mid) forms an inversion with arr[j]. This counts all inversions across the split boundary in $O(n)$ total.

When to Use Divide and Conquer

D&C is the right choice when:

  • The problem naturally splits into independent subproblems of the same type. If you can halve the input and solve each half separately, D&C is worth exploring.
  • The combine step is efficient. If combining subproblem solutions takes $O(n)$ or less, the overall algorithm benefits from the logarithmic recursion depth.
  • Parallelism matters. Because subproblems are independent, D&C algorithms map naturally to parallel execution. Fork both recursive calls, join on the combine step.
  • You need to improve on $O(n^2)$. Many problems with naïve $O(n^2)$ solutions have $O(n \log n)$ D&C alternatives.

When NOT to Use Divide and Conquer

  • Subproblems overlap. If solving the left half and right half share common sub-computations, you are doing redundant work. Switch to dynamic programming, which caches results.
  • The combine step is expensive. If merging solutions takes $O(n^2)$, the logarithmic depth doesn’t save you.
  • The base case dominates. If the problem doesn’t shrink meaningfully or the recursion overhead exceeds the benefit, an iterative approach wins.

Interviewer Tips

  1. State the three steps explicitly. When presenting a D&C solution, say “I divide by…, I conquer by…, I combine by…” Interviewers want to see structured thinking.
  2. Write the recurrence. Every D&C solution has a recurrence. Write it out, then apply the Master Theorem. This demonstrates mathematical rigor.
  3. Compare with alternatives. For maximum subarray, mention Kadane’s algorithm. For closest pair, acknowledge the brute-force baseline. Showing awareness of trade-offs signals maturity.
  4. Watch for off-by-one errors. The midpoint calculation mid = left + (right - left) / 2 avoids overflow. The ranges [left, mid] and [mid+1, right] must not overlap or leave gaps.
  5. Practice the merge step. The divide step is usually trivial (split in half). The combine step is where bugs hide. Test it with small examples — arrays of size 2 and 3 reveal most merge issues.