cf.completefrontend
RECURSION & BACKTRACKING · CORE

Divide and conquer

Split a problem into smaller halves, solve each half the same way, and combine the two answers into the answer for the whole.

Time O(n log n)Space O(log n)7 practice problemsStep-through picture

The idea

Divide and conquer solves a big problem by splitting it into smaller problems of the same kind. It solves each smaller problem with the same method, again by splitting, until the pieces are so small the answer is obvious. Then it combines the small answers into bigger ones.

Take this question: in [-2, 1, -3, 4, -1, 2, 1, -5], which run of neighboring items has the largest sum? Split the list in the middle. The best run is either fully in the left half, fully in the right half, or it crosses the middle. The first two are the same question on a smaller list. The third is easy: grow a run out from the middle to the left and to the right.

The three parts always appear: a base case (one item), a split (find mid, solve both halves), and a combine step. Merge sort, quick sort, and binary search all follow this shape.

An everyday example

Counting votes in a large election

No single person counts every vote in a country. The country splits into regions, regions into towns, towns into polling stations. Each station counts its own small pile. Then towns add up their stations, regions add up their towns, and the country adds up its regions. Every level does the same simple job: split the work, wait for the answers, and combine them.

How the example maps to the code
In the exampleIn the code
One polling station counting its pileThe base case: if (low === high) return nums[low]
Splitting a region into two partsmid = Math.floor((low + high) / 2)
Each part counts on its ownmaxSubarraySum(nums, low, mid) and maxSubarraySum(nums, mid + 1, high)
Adding up the parts' resultsMath.max(leftBest, rightBest, leftReach + rightReach)

From the slow way to divide and conquer

  1. The obvious way to find the run of neighboring items with the largest sum: try every pair of ends. For each start i, extend the run one item at a time and keep a running sum. That's about n² / 2 sums, which is 5 billion for 100,000 items. Every pair is looked at, even though most runs are clearly bad.
  2. Cut the list in the middle, at mid. Any run in it is in one of three places: fully in the left half, fully in the right half, or crossing the middle, which means it holds both mid and mid + 1. The first two are the same question on a list half as long, so the function can call itself on each half.
  3. The crossing case is the new part, and it is easier than it looks. A crossing run is a left piece that ends at mid plus a right piece that starts at mid + 1. The two pieces don't affect each other, so pick each one separately: grow left from mid and keep the best sum as leftReach, grow right from mid + 1 and keep rightReach. One pass over the range finds both.
  4. Now count the cost. Each level of splitting does one pass over its ranges, n steps in total, and halving reaches one-item ranges after about log n levels. So the work is n log n instead of n². Stop at one item, whose best run is itself, and return the largest of the three answers at every level. That recursion is divide and conquer.

How it works

  1. Work on a range of the list, from index low to index high.
  2. Base case: if low === high, the range has one item, and the best run is that item.
  3. Split: mid = Math.floor((low + high) / 2).
  4. Solve each half with the same function: leftBest for low..mid, rightBest for mid + 1..high.
  5. Combine, part 1: grow a run left from mid and keep the best sum in leftReach.
  6. Combine, part 2: grow a run right from mid + 1 and keep the best sum in rightReach.
  7. Return the largest of leftBest, rightBest, and leftReach + rightReach.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function maxSubarraySum(nums, low = 0, high = nums.length - 1) {
  2. if (low === high) return nums[low];
  3. const mid = Math.floor((low + high) / 2);
  4. const leftBest = maxSubarraySum(nums, low, mid);
  5. const rightBest = maxSubarraySum(nums, mid + 1, high);
  6. let sum = 0;
  7. let leftReach = -Infinity;
  8. for (let i = mid; i >= low; i--) {
  9. sum += nums[i];
  10. leftReach = Math.max(leftReach, sum);
  11. }
  12. sum = 0;
  13. let rightReach = -Infinity;
  14. for (let i = mid + 1; i <= high; i++) {
  15. sum += nums[i];
  16. rightReach = Math.max(rightReach, sum);
  17. }
  18. return Math.max(leftBest, rightBest, leftReach + rightReach);
  19. }

How fast it is

TimeO(n log n)
Extra memoryO(log n)

There are about log n levels of halving, and each level does n steps of combine work in total. The call chain is one call per level, so log n deep.

  • Best caseO(n log n)

    Every input of size n: the code always splits down to single items and always runs both combine loops. Only a single item finishes at once, in one call.

  • Average caseO(n log n)

    Any values. Positive, negative, or mixed, the number of calls is always 2n - 1 and each level's loops cover n items.

  • Worst caseO(n log n)

    Any input, such as 1,000,000 items: about 20 levels, each with about 1,000,000 steps of combine work, or 20 million steps instead of a trillion.

Common mistakes

  • Splitting into low..mid - 1 and mid..high with mid rounded down. When high = low + 1, mid equals low and one side is empty, which breaks the base case.
  • Forgetting the crossing case and only taking the larger half. A best run that spans the middle is missed.
  • Starting the crossing sums at 0 instead of -Infinity. In an all-negative list, the answer would wrongly become 0.
  • Copying the halves with slice on every call. That adds a lot of memory. Pass low and high instead.

When to use it

Look for these clues in a problem:

  • The answer for a list can be built from the answers for its two halves plus something that crosses the middle.
  • A simple method is O(n²) and the question hints at O(n log n).
  • The problem is about splitting: a range, an expression around an operator, or points split by a line.
  • The same question naturally applies to a smaller piece of the input.

Check yourself

Answer each one in your head first, then open it.

How many calls does maxSubarraySum make for 5 items?

9, which is 2n - 1: 5 one-item calls and 4 calls that split and combine.

Why do leftReach and rightReach start at -Infinity instead of 0?

Starting at 0 would act like an empty piece is allowed. For [-7, -3, -9] the answer would wrongly be 0 instead of -3.

Why must a crossing run contain both mid and mid + 1?

A run is a block of neighbors. If it has items on both sides of the cut, it must pass through the two items next to the cut. Otherwise it lies fully on one side.

In the trace, why is the answer for 0..2 equal to 4 and not the crossing sum 1?

A crossing run there must include index 1, the -5, and the best one is [2, -5, 4] with sum 1. The single item 4, found as rightBest, is larger, so it wins.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The claim: maxSubarraySum(nums, low, high) returns the largest sum of a non-empty run inside low..high. For one item, it's true, because the only run is the item. For longer ranges, assume the claim holds for both halves, which are shorter. Then leftBest and rightBest are the best runs fully inside each half.

The three cases cover every run: a run either ends at or before mid, or starts at or after mid + 1, or contains both mid and mid + 1. A crossing run's sum is the sum of its left piece, ending at mid, plus its right piece, starting at mid + 1. The loops try every possible left piece and every possible right piece and keep the best of each, so leftReach + rightReach is the best crossing sum. The largest of the three is the best run overall.

The recursion always ends. When low < high, mid = Math.floor((low + high) / 2) satisfies low <= mid < high, so both halves are non-empty and strictly shorter. Every chain of calls reaches a one-item range. The halves are solved first, then combined, so each combine step uses answers that are already correct.

Going deeper

3 more ideas

Why three cases cover every possible run

Any run of neighboring items in low..high either ends at or before mid (fully left), starts after mid (fully right), or includes both mid and mid + 1 (crossing). There is no fourth option. A crossing run is a left piece ending at mid plus a right piece starting at mid + 1, and the two pieces can be chosen separately, so the best crossing run is leftReach + rightReach.

Why it costs O(n log n)

Halving n items until each piece has one item takes about log n levels. On each level, the combine loops together walk over all n items once. So the total work is n per level times log n levels. For 1,000,000 items that is about 20 million steps, instead of a trillion for checking every pair of ends.

When the split isn't in the middle

Some problems split around something other than the middle. To find all values of 2*3-4*5 with different brackets, split at each operator, solve the left and right sides, and combine every left value with every right value. To find the closest pair of points, split by an x coordinate. The shape is the same: smaller copies of the problem plus a combine step.

Work it by hand

Every step in a table, with why

Find the largest run sum in 5 numbers. Each row is one call, listed in the order the calls finish, so a range's two halves always come before it.

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

Steplow..highmidleftBestrightBestleftReach + rightReachReturnsWhy
10..0----2The first call splits down to the leftmost single item. A one-item range returns that item.
21..1-----5The other single item of the range 0..1.
30..102-52 + -5 = -32Crossing must use both 2 and -5, giving -3. The left half alone, 2, is better.
42..2----4The right half of 0..2 is one item.
50..2124-3 + 4 = 14Growing left from index 1 gives sums -5, then -3, so leftReach = -3. Crossing gives 1, but 4 alone is best.
63..3-----1Now the right half of the whole list, 3..4, splits into two single items.
74..4----3The last single item.
83..43-13-1 + 3 = 23Crossing gives 2, less than 3 alone.
90..42434 + 2 = 66Growing left from index 2: 4, -1, 1, so leftReach = 4. Growing right from index 3: -1, 2, so rightReach = 2. The crossing run [4, -1, 3] sums to 6 and beats both halves.

It returns 6, from the run [4, -1, 3]. Neither half held it: the best fully-left run was 4 and the best fully-right run was 3. The recursion made 2 × 5 - 1 = 9 calls and ends when the top call, 0..4, combines its halves.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Divide and conquerO(n log n)O(log n)You want to practice the split, solve, combine shape, or the problem has a combine step that needs a pass over the range.
Every pair of ends with a running sumO(n²)O(1)The list is tiny, or you want a simple version to test a faster one against.
Kadane's scanO(n)O(1)You only need the answer for the whole list once. It is the fastest and shortest.
Divide and conquer with four valuesO(n)O(log n)You want the split shape at linear time, or you plan to store the four values in a segment tree for range questions with updates.

Extra memory: O(log n): the call chain is one call per level of halving. Passing low and high instead of copying halves keeps it that small.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Divide and conquer and the other approaches, on a scale where each line up is 10 times more steps.
  • Divide and conquer O(n log n)
  • Every pair of ends with a running sum O(n²)
  • Kadane's scan, Divide and conquer with four values O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Divide and conquer339,96620 million
Every pair of ends with a running sum1001 million1 trillion
Kadane's scan101,0001 million
Divide and conquer with four values101,0001 million

Inputs that need care

5 tricky inputs
An empty list: nums = []
high starts at -1, low === high is never true, and the function keeps calling itself on the same range until the engine throws a RangeError. Check nums.length === 0 first and return whatever the problem asks for.
All negative: nums = [-7, -3, -9]
It returns -3, the single largest item. This works because leftReach and rightReach start at -Infinity, so an empty run, with sum 0, is never counted.
One item: nums = [8]
low === high on the first call, so it returns 8 with no splitting.
An odd length, such as 5 items
mid rounds down, so the left half gets the extra item: 0..2 and 3..4. Both halves are still non-empty, so the base case is always reached.
Very large sums
JavaScript numbers are exact only up to Number.MAX_SAFE_INTEGER, about 9 × 10^15. If sums can pass that, use BigInt values.

Variations and follow-ups

Twists interviewers add

Return four values to get O(n)

Let each call return the range's total, its best prefix, its best suffix, and its best run. The parent computes all four from its children's values in O(1), with no loops. The time becomes O(n), and this is exactly what a segment tree node stores to answer this question for any range.

Kadane's scan

Walk once from left to right, keeping the best sum of a run that ends at the current item: either extend the previous run or start fresh. It is O(n) time and O(1) space, and is the usual answer when the list is given all at once.

Count across the middle

The same shape counts pairs that cross the middle. Merge sort can count inversions, pairs where a bigger item comes first, by counting during each merge how many left items are bigger than each right item.

Return the run, not only the sum

Carry the start index with leftReach and the end index with rightReach, and return the indexes along with the best sum from each call. The parent picks the indexes of whichever case wins.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the answer for a list can be built from its two halves plus something that crosses the middle, or when the brute force is O(n²) and the hint is O(n log n).
  • State the three cases out loud before coding: fully left, fully right, and crossing. Then explain why the crossing case is two separate loops: the left piece and the right piece don't affect each other.
  • Test one item, an all-negative list, and two items where the best run crosses the middle, like [3, 4]. Each tests a different line of the code.
  • Give the time with a recurrence: T(n) = 2T(n/2) + n, two half-size calls plus a linear combine, which works out to O(n log n).
  • The usual follow-up is "can you do better?". Answer with Kadane's scan, or with the four-value version, which turns the combine step into O(1) and the whole thing into O(n).

Where frontend code uses it

The same idea in real UI code
  • V8 sorts arrays with TimSort, which is built on merging sorted runs, a divide-and-conquer idea.
  • Web map libraries split the world into tiles: each zoom level divides every tile into four smaller tiles, so the map only loads the tiles in view.
  • Canvas and game engines often store shapes in a quadtree, which keeps dividing the screen into four parts so hit tests only look at shapes in the right part.

Related algorithms