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 problemAs a picture:
Problem (size n)
/ \
Divide Divide
/ \
Subproblem (n/2) Subproblem (n/2)
| |
Conquer Conquer
| |
Answer (left) Answer (right)
\ /
\ /
Combine → Final answerBecause 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 maxThe 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 answerclass 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: 9Of 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 combineBinary 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 mergeFor Binary Search:
T(n) = T(n/2) + O(1)
1 subproblem of size n/2, plus O(1) for one comparisonThe 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 nEach 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 workCompare 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⁰ = 1The 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 = 1Each 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 6The 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 atmidgo right from
mid + 1, tracking the best sum starting atmid + 1add 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 = 6class 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: 6The 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) → 3Checking 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 halfThe 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 = 3class 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]: 3A 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, combinesvs 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; // safe3. 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)orO(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:
Pow(x, n) (LeetCode 50) – watch out for negative
nMaximum Subarray (LeetCode 53) – try both divide and conquer and Kadane
Sort an Array (LeetCode 912) – using Merge Sort
Kth Largest Element in an Array (LeetCode 215) – Quickselect
Count of Smaller Numbers After Self (LeetCode 315) – merge sort counting
Reverse Pairs (LeetCode 493) – a harder inversion-count variant
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 answersIts 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).