Chapter 58 of 65

Divide and Conquer

Imagine your teacher gives you a stack of 1,000 answer sheets to sort by roll number.

Sorting all 1,000 alone is painful. So you split the stack into two halves and give each half to a friend. Each friend splits their half again and passes it on. Eventually, someone gets a stack of just one sheet, which is already "sorted".

Then the sorted piles are merged back together, two at a time, until you have one fully sorted stack.

This strategy has a name: Divide and Conquer.

Divide and Conquer is a problem-solving technique that breaks a problem into smaller independent subproblems of the same type, solves them recursively, and combines their answers to solve the original problem.

You have already used it: Binary Search, Merge Sort and Quick Sort are all divide and conquer algorithms. In this chapter, we look at the technique itself, so you can recognise it and use it on new problems.


The Three Steps

Every divide and conquer algorithm has three steps:

1. DIVIDE   → Split the problem into smaller subproblems
2. CONQUER  → Solve each subproblem recursively
              (if it is small enough, solve it directly: the base case)
3. COMBINE  → Merge the sub-answers into the answer for the whole problem

As a picture:

                 Problem (size n)
                 /              \
          Divide                  Divide
             /                      \
   Subproblem (n/2)          Subproblem (n/2)
        |                           |
     Conquer                     Conquer
        |                           |
   Answer (left)              Answer (right)
             \                      /
              \                    /
               Combine → Final answer

Because the subproblems are the same type as the original problem, divide and conquer is naturally written using recursion (see the Recursion chapter).


A First Example: Finding the Maximum

Let's find the largest element of an array using divide and conquer.

[3, 8, 2, 9, 4, 7]

The three steps:

Divide:  split into left half and right half
Conquer: find the max of each half (recursively)
Combine: answer = max(leftMax, rightMax)
Base:    one element → that element is the max

The recursion looks like this:

               [3, 8, 2, 9, 4, 7]
               /                \
        [3, 8, 2]              [9, 4, 7]
        /       \              /       \
    [3, 8]     [2]         [9, 4]     [7]
    /    \                 /    \
  [3]   [8]              [9]   [4]

Combine upwards:
max(3, 8) = 8      max(8, 2) = 8
max(9, 4) = 9      max(9, 7) = 9
max(8, 9) = 9  ← final answer
class Main {

    static int findMax(int[] arr, int low, int high) {

        // Base case: only one element
        if (low == high) {
            return arr[low];
        }

        // Divide
        int mid = low + (high - low) / 2;

        // Conquer
        int leftMax = findMax(arr, low, mid);
        int rightMax = findMax(arr, mid + 1, high);

        // Combine
        return Math.max(leftMax, rightMax);
    }

    public static void main(String[] args) {

        int[] arr = {3, 8, 2, 9, 4, 7};

        System.out.println("Maximum: " + findMax(arr, 0, arr.length - 1));
    }
}

Output:

Maximum: 9

Of course, a simple loop also finds the maximum in O(n). This example is only to show the structure clearly. The real power of divide and conquer appears when the combine step is clever, as we will see next.


Algorithms You Already Know

Algorithm

Divide

Conquer

Combine

Time

Binary Search

Compare with middle element

Search only ONE half

Nothing to combine

O(log n)

Merge Sort

Split at the middle (easy)

Sort both halves

Merge two sorted halves (the real work)

O(n log n)

Quick Sort

Partition around a pivot (the real work)

Sort both parts

Nothing to combine

O(n log n) average, O(n²) worst

Notice the interesting contrast:

Merge Sort → easy divide, hard combine
Quick Sort → hard divide, easy combine

Binary Search solves only one of the two halves. Some books call this special case decrease and conquer.


Analysing Divide and Conquer: Recurrence Relations

The running time of a divide and conquer algorithm is described by a recurrence relation: a formula that defines T(n) using T of smaller inputs.

T(n) = (number of subproblems) × T(size of each subproblem) + (cost of dividing and combining)

For Merge Sort:

T(n) = 2T(n/2) + O(n)

2 subproblems, each of size n/2, plus O(n) to merge

For Binary Search:

T(n) = T(n/2) + O(1)

1 subproblem of size n/2, plus O(1) for one comparison

The Recursion Tree Method

Let's solve the Merge Sort recurrence by drawing the work done at each level:

Level 0:            n                     → work n
Level 1:        n/2     n/2               → work n
Level 2:     n/4  n/4  n/4  n/4           → work n
  ...
Level k:     2ᵏ pieces, each of size n/2ᵏ → work n
  ...
Last level:  1  1  1  ...  1  (n pieces)  → work n

Each level does n work in total, and the size halves at every level, so there are about log₂ n levels.

Total = n × log₂ n = O(n log n)

The Master Theorem (Simple Form)

Many divide and conquer recurrences have this shape:

T(n) = a · T(n / b) + O(nᵈ)

a = number of subproblems
b = factor by which the size shrinks
d = exponent of the divide + combine work

Compare d with log_b(a):

Case

Result

Meaning

d > log_b(a)

T(n) = O(nᵈ)

The top-level combine work dominates

d = log_b(a)

T(n) = O(nᵈ log n)

Every level does equal work

d < log_b(a)

T(n) = O(n^(log_b a))

The huge number of small subproblems dominates

Applying it:

Algorithm

Recurrence

a, b, d

Result

Binary Search

T(n/2) + O(1)

1, 2, 0 (log₂1 = 0 = d)

O(log n)

Merge Sort

2T(n/2) + O(n)

2, 2, 1 (log₂2 = 1 = d)

O(n log n)

findMax above

2T(n/2) + O(1)

2, 2, 0 (log₂2 = 1 > d)

O(n)

Fast power (below)

T(n/2) + O(1)

1, 2, 0

O(log n)

Karatsuba multiplication

3T(n/2) + O(n)

3, 2, 1 (log₂3 ≈ 1.585 > d)

O(n^1.585)

The Master Theorem only works when the subproblems are all the same fraction of the input. Quick Sort's worst case, T(n) = T(n - 1) + O(n), does not fit this shape; summing n + (n-1) + ... + 1 gives O(n²).


Problem 1: Fast Power (Exponentiation by Squaring)

Problem: Compute xⁿ.

The simple way multiplies x by itself n times, which is O(n). Divide and conquer does much better using this fact:

If n is even:  xⁿ = x^(n/2) × x^(n/2)
If n is odd:   xⁿ = x^(n/2) × x^(n/2) × x      (n/2 is integer division)
Base case:     x⁰ = 1

The key trick is to compute x^(n/2) only once and reuse it.

2¹⁰ = 2⁵ × 2⁵
2⁵  = 2² × 2² × 2
2²  = 2¹ × 2¹
2¹  = 2⁰ × 2⁰ × 2
2⁰  = 1

Only 5 recursive calls (about log₂ n) instead of 10 multiplications.
class Main {

    static long power(long x, int n) {

        // Base case
        if (n == 0) {
            return 1;
        }

        // Divide: solve the half-size problem only once
        long half = power(x, n / 2);

        // Combine
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }

    public static void main(String[] args) {

        System.out.println("2^10 = " + power(2, 10));
        System.out.println("3^13 = " + power(3, 13));
        System.out.println("5^0  = " + power(5, 0));
    }
}

Output:

2^10 = 1024
3^13 = 1594323
5^0  = 1

Each call halves n, so:

Time  → O(log n)
Space → O(log n)   (recursion stack)

A very common mistake is writing:

return power(x, n / 2) * power(x, n / 2);   // two recursive calls!

This makes two recursive calls of half size: T(n) = 2T(n/2) + O(1), which is O(n). All the benefit is lost.

(In real problems, the result is usually taken modulo a number like 1_000_000_007 to avoid overflow. Without it, long overflows once the answer is larger than about 9.2 × 10¹⁸.)


Problem 2: Maximum Subarray Sum

Problem: Find the largest possible sum of a contiguous subarray.

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Best subarray: [4, -1, 2, 1] → sum 6

The Divide and Conquer Idea

Split the array at the middle. The best subarray must be in one of three places:

          left half       |       right half
    [ -2, 1, -3, 4, -1 ]  |  [ 2, 1, -5, 4 ]

1. Entirely in the left half    → solve recursively
2. Entirely in the right half   → solve recursively
3. Crossing the middle          → solve directly in O(n)

For the crossing case, the subarray must include arr[mid] and arr[mid + 1]. So we:

  • go left from mid, tracking the best sum ending at mid

  • go right from mid + 1, tracking the best sum starting at mid + 1

  • add the two

For our array (mid = 4, the element -1):

Going left from index 4:
-1 → 3 → 0 → 1 → -1        best = 3  (4 + -1)

Going right from index 5:
2 → 3 → -2 → 2              best = 3  (2 + 1)

Crossing sum = 3 + 3 = 6
class Main {

    static int maxCrossingSum(int[] arr, int low, int mid, int high) {

        // Best sum of a subarray that ends exactly at mid
        int sum = 0;
        int leftBest = Integer.MIN_VALUE;

        for (int i = mid; i >= low; i--) {
            sum += arr[i];
            leftBest = Math.max(leftBest, sum);
        }

        // Best sum of a subarray that starts exactly at mid + 1
        sum = 0;
        int rightBest = Integer.MIN_VALUE;

        for (int i = mid + 1; i <= high; i++) {
            sum += arr[i];
            rightBest = Math.max(rightBest, sum);
        }

        return leftBest + rightBest;
    }

    static int maxSubarray(int[] arr, int low, int high) {

        if (low == high) {
            return arr[low];
        }

        int mid = low + (high - low) / 2;

        int leftSum = maxSubarray(arr, low, mid);
        int rightSum = maxSubarray(arr, mid + 1, high);
        int crossSum = maxCrossingSum(arr, low, mid, high);

        return Math.max(Math.max(leftSum, rightSum), crossSum);
    }

    public static void main(String[] args) {

        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        System.out.println("Maximum subarray sum: " + maxSubarray(arr, 0, arr.length - 1));
    }
}

Output:

Maximum subarray sum: 6

The recurrence is the same as Merge Sort:

T(n) = 2T(n/2) + O(n)  →  O(n log n)

This problem can also be solved in O(n) with Kadane's algorithm, which interviewers usually expect as the final answer. But the divide and conquer version is a classic exercise in designing the combine step, and it is sometimes asked directly.


Problem 3: Counting Inversions

An inversion is a pair of positions i < j where arr[i] > arr[j]. It measures how far an array is from being sorted.

[2, 4, 1, 3, 5]

Inversions: (2, 1), (4, 1), (4, 3) → 3

Checking all pairs takes O(n²). With divide and conquer, we can do it in O(n log n) by piggybacking on Merge Sort.

The Idea

Total inversions = inversions inside the left half
                 + inversions inside the right half
                 + inversions with one element in each half

The third part is counted during the merge step. Both halves are already sorted. When we take an element from the right half because it is smaller than left[i], it is also smaller than every remaining element in the left half:

For example, suppose we are merging these two sorted halves:

left  = [2, 4]      right = [1, 3, 5]
         i                   j

1 < 2 → take 1 from right.
        Both 2 and 4 are greater than 1 → add 2 inversions

left  = [2, 4]      right = [1, 3, 5]
         i                      j

2 < 3 → take 2, no inversion

left  = [2, 4]      right = [1, 3, 5]
            i                   j

3 < 4 → take 3 from right.
        Only 4 remains in left → add 1 inversion

Total cross inversions = 3
class Main {

    static long mergeAndCount(int[] arr, int low, int mid, int high) {

        int[] temp = new int[high - low + 1];

        int i = low;
        int j = mid + 1;
        int k = 0;

        long count = 0;

        while (i <= mid && j <= high) {

            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                // arr[i..mid] are all greater than arr[j]
                count += (mid - i + 1);
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= high) {
            temp[k++] = arr[j++];
        }

        for (int t = 0; t < temp.length; t++) {
            arr[low + t] = temp[t];
        }

        return count;
    }

    static long countInversions(int[] arr, int low, int high) {

        if (low >= high) {
            return 0;
        }

        int mid = low + (high - low) / 2;

        long count = 0;

        count += countInversions(arr, low, mid);
        count += countInversions(arr, mid + 1, high);
        count += mergeAndCount(arr, low, mid, high);

        return count;
    }

    public static void main(String[] args) {

        int[] arr = {8, 4, 2, 1};
        System.out.println("Inversions in [8, 4, 2, 1]: " + countInversions(arr, 0, arr.length - 1));

        int[] arr2 = {2, 4, 1, 3, 5};
        System.out.println("Inversions in [2, 4, 1, 3, 5]: " + countInversions(arr2, 0, arr2.length - 1));
    }
}

Output:

Inversions in [8, 4, 2, 1]: 6
Inversions in [2, 4, 1, 3, 5]: 3

A fully reversed array of n elements has the maximum possible n(n-1)/2 inversions. For [8, 4, 2, 1], that is 4 × 3 / 2 = 6.

We use long for the count because, for n = 100,000, the count can reach about 5 × 10⁹, which does not fit in an int.

Note that this function also sorts the array as a side effect.

Time  → O(n log n)
Space → O(n)

More Famous Divide and Conquer Algorithms

Algorithm

What it does

Time

Karatsuba multiplication

Multiplies two n-digit numbers using 3 half-size multiplications instead of 4

O(n^1.585)

Strassen's algorithm

Multiplies two matrices using 7 half-size multiplications instead of 8

O(n^2.807)

Closest pair of points

Finds the two nearest points in a plane

O(n log n)

Quickselect

Finds the k-th smallest element (Quick Sort idea, recurse into one side)

O(n) average


Divide and Conquer vs Other Techniques

vs Greedy

Greedy:             one choice per step, never splits the problem
Divide and Conquer: splits into subproblems, solves ALL of them, combines

vs Dynamic Programming

Divide and conquer works best when the subproblems are independent (they do not overlap). Merge Sort's left half and right half share nothing.

Now look at the naive recursive Fibonacci:

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)

fib(3) is computed twice, fib(2) three times, ...

Here the subproblems overlap, and plain divide and conquer repeats the same work again and again, giving exponential time. Storing and reusing these answers is the core idea of Dynamic Programming, which is the topic of the next chapter.

Technique

Subproblems

Examples

Divide and Conquer

Independent, usually split in halves

Merge Sort, Quick Sort, Binary Search

Dynamic Programming

Overlapping, answers are reused

Fibonacci, Knapsack, LCS

Greedy

One subproblem after one local choice

Activity selection, Kruskal, Dijkstra


Common Mistakes

1. Missing or Wrong Base Case

Without a correct base case (like low == high or n == 0), the recursion never stops and you get a StackOverflowError.

2. Overflow When Finding the Middle

int mid = (low + high) / 2;          // can overflow for huge indexes
int mid = low + (high - low) / 2;    // safe

3. Recomputing the Same Subproblem

As in the fast power example, calling power(x, n / 2) twice destroys the speed-up. Store the result in a variable.

4. Off-by-One Errors When Splitting

Use [low, mid] and [mid + 1, high]. Splitting as [low, mid - 1] and [mid, high] can cause infinite recursion on a 2-element range when mid == low.

5. An Expensive Combine Step

If combining costs O(n²), the whole algorithm becomes O(n²) even with perfect splitting. The combine step is where the design effort should go.

6. Copying Subarrays Unnecessarily

Creating new arrays for every half (for example with Arrays.copyOfRange) adds extra time and memory. Passing low and high indexes is usually better.


Interview Tips and Practice Problems

  • When you see "sorted", "halves", or a required time of O(log n) or O(n log n), think about divide and conquer.

  • Always describe the three steps clearly: what you divide, what you solve recursively, and how you combine.

  • Be ready to write the recurrence and solve it with the Master Theorem.

Good problems to practice:

  1. Pow(x, n) (LeetCode 50) – watch out for negative n

  2. Maximum Subarray (LeetCode 53) – try both divide and conquer and Kadane

  3. Sort an Array (LeetCode 912) – using Merge Sort

  4. Kth Largest Element in an Array (LeetCode 215) – Quickselect

  5. Count of Smaller Numbers After Self (LeetCode 315) – merge sort counting

  6. Reverse Pairs (LeetCode 493) – a harder inversion-count variant

  7. Count Inversions (GeeksforGeeks)


The Main Idea

Divide and Conquer solves a problem by splitting it into smaller independent subproblems of the same kind.

Divide   → split the problem (usually into halves)
   ↓
Conquer  → solve each part recursively (base case solves tiny parts)
   ↓
Combine  → merge the partial answers

Its running time is written as a recurrence:

T(n) = a · T(n/b) + O(nᵈ)

and the most common results are:

T(n) = T(n/2)  + O(1)  → O(log n)      (Binary Search, Fast Power)
T(n) = 2T(n/2) + O(1)  → O(n)          (findMax)
T(n) = 2T(n/2) + O(n)  → O(n log n)    (Merge Sort, Inversions)

Remember these four things:

1. Every D&C algorithm has Divide, Conquer and Combine steps.
2. A correct base case is essential.
3. The combine step is where the cleverness lives.
4. If subproblems overlap, use Dynamic Programming instead.

When a problem can be split into independent halves whose answers can be merged efficiently, divide and conquer often turns an O(n²) solution into O(n log n).