Divide and conquer and selection

The shape: split, solve, combine

Some problems get easier when the input is cut in two. Cut it, solve each half as if it were the whole problem, and stitch the two answers into the answer for the whole. That is divide and conquer, and it has exactly three moving parts: a split that makes two smaller instances of the same problem, a base case small enough to answer on sight, and a combine step that turns the two sub-answers into one. If you can say what each part is, you can write the function; the first two are usually a line each, and almost all of the thinking goes into the third.

function solve(lo, hi) {                          // answers the question for the half-open range [lo, hi)
  if (hi - lo <= 1) return baseCase(lo, hi);      // size 0 or 1: answer on sight
  const mid = lo + ((hi - lo) >> 1);
  const left = solve(lo, mid);                    // divide: two independent halves
  const right = solve(mid, hi);
  return combine(left, right, lo, mid, hi);       // the whole difficulty lives here
}

Two properties make this different from the recursion you have already seen. The subproblems are independent: the left half never needs anything the right half computed, so they can be solved in either order, and the only place the two meet is the combine. And they are disjoint: no piece of the input is solved twice. When subproblems overlap (the same smaller question reached by several routes) you are in dynamic programming territory, covered in DP in one dimension, and a cache is what saves you, not the split. Backtracking is another relative: it also recurses, but it explores choices and undoes them, rather than splitting the data in two.

This chapter assumes the recursion and sorting chapters. Merge sort, quickselect, counting inversions and the n log n lower bound already live in the sorting chapter, and this chapter does not repeat them; it uses them as the worked examples of a pattern and then applies the pattern to problems that sorting alone does not solve.

Where you have already used it

The pattern is older than this chapter. Looking at the algorithms you know as instances of it shows the one design question that separates them: where does the work happen, before the recursive calls or after them?

Merge sort does its work in the combine (after the calls); quicksort does it in the split (before the calls) and has an empty combine. The problems below all look like merge sort: the split is trivial (cut in the middle) and the combine is where the question gets answered. One more fact from the sorting chapter is worth keeping in mind as a ceiling: no comparison-based method can sort in fewer than about n log₂ n comparisons, so a divide-and-conquer sort that reaches O(n log n) is as good as comparison sorting gets.

Reading the recurrence off the code

Once you have a divide-and-conquer function you can read its running time straight from its shape, without a theorem. Write down three numbers: a, the number of recursive calls; b, the factor by which the input shrinks (2 for a halving); and f(n), the work done outside the recursive calls (the combine plus any splitting). The cost obeys T(n) = a · T(n/b) + f(n). The complexity chapter states the master theorem for this; here is the picture behind it, which is easier to remember than three cases.

Draw the recursion tree. At depth k there are aᵏ calls, each on an input of size n/bᵏ. So the work done at depth k is the number of calls times the work per call, aᵏ · f(n/bᵏ), and the total is the sum over all depths, about log_b n of them. When f(n) is n^d, the work at depth k is n^d times (a / bd)ᵏ, so everything depends on one ratio r = a / bd:

• r < 1: each level does less than the one above it, the sum is a shrinking geometric series, and the root dominates: T(n) = O(n^d), just the top-level combine.
• r = 1: every level does the same work, so the total is the work per level times the number of levels: O(n^d · log n). Merge sort is here, with n work on each of log₂ n levels.
• r > 1: each level does more than the one above, and the leaves dominate. There are a^{log_b n} = n^{log_b a} of them, so T(n) = O(n^{log_b a}).

The last two rows are why the recurrence is worth reading: in both, the combine is cheap and the whole improvement comes from lowering a by one. The quickselect row is the idealized best case; the sorting chapter proves the average for a random pivot. The recurrence assumes equal-sized halves: the merge sort bound needs the split to be balanced, and the next paragraphs show what happens when it is not.

Three ways the code costs more than the recurrence you meant to write. First, a lopsided split. Quicksort with a pivot that peels off one element has T(n) = T(n − 1) + n, which is n²/2 steps, not n log n. Second, copying in the split. This version of "largest element" copies each half:

function maxSliced(nums) {
  if (nums.length === 1) return nums[0];
  const mid = nums.length >> 1;
  return Math.max(maxSliced(nums.slice(0, mid)), maxSliced(nums.slice(mid)));   // copies every element, every level
}

function maxRange(nums, lo = 0, hi = nums.length) {
  if (hi - lo === 1) return nums[lo];
  const mid = lo + ((hi - lo) >> 1);
  return Math.max(maxRange(nums, lo, mid), maxRange(nums, mid, hi));            // passes indexes, copies nothing
}

The recurrence for the range version is 2T(n/2) + 1, which is O(n). The sliced version pays n elements of copying per level, so it is 2T(n/2) + n, which is O(n log n); for 1,024 elements the slices copy 10,240 elements in total, and the range version copies none. This is the same cost the recursion chapter warned about for slice, and the cure is the same: pass index ranges.

Third, a combine that does more than you think. A combine that sorts the merged pieces again costs n log n per level, so the recurrence is 2T(n/2) + n log n and the total is O(n log² n): there are log n levels and each does about n log n. The closest-pair algorithm below has exactly this trap, and carrying the sorted order up from the recursion is how it avoids it.

Finding the combine step

The method for any new problem: pretend the two recursive calls have already come back with the right answer for the left half and the right half, and ask what could the answer for the whole range be that neither half can see? The candidates fall into three families.

1. The answer lives in one half. Take the better of the two sub-answers (the maximum of an array, the winning candidate). The combine is O(1), or it checks which half to keep.
2. The answer may straddle the split. The halves report their own best, and the combine must find the best thing that uses both sides: a subarray that crosses the middle, a pair with one point on each side. This is the family of most of the problems below.
3. The answer is built from both. The sub-answers are not candidates but ingredients: two outlines to merge into one, two lists of results to pair up.

The extra fact is a design choice: the recursive call may return more than the original question asks for. Merge sort returns the sorted half because the combine needs it sorted. The maximum-subarray version below returns four numbers per range instead of one, because the combine needs the best prefix and suffix. When your combine is stuck, ask what extra fact about each half would make it easy, and have the recursion return that too.

Maximum subarray, and why Kadane wins

Find the contiguous subarray with the largest sum. The array has n(n + 1)/2 subarrays, so checking every one is O(n²), even with a running sum for each start. Cut the array at the middle and ask where the best subarray can be. Either it lies entirely in the left half, or entirely in the right half, or it crosses the middle, which means it contains both nums[mid - 1] and nums[mid]. The first two are the recursive calls. For the third, notice that a crossing subarray is a piece of the left half that ends at mid - 1 glued to a piece of the right half that starts at mid, and the two pieces are chosen independently. So the best crossing sum is the best suffix of the left half plus the best prefix of the right half, each found by one scan outward from the middle.

function maxSubarrayDC(nums) {
  if (nums.length === 0) throw new RangeError("needs at least one element");
  function best(lo, hi) {                          // best sum of a non-empty subarray inside [lo, hi)
    if (hi - lo === 1) return nums[lo];
    const mid = lo + ((hi - lo) >> 1);
    let sum = 0, leftBest = -Infinity;
    for (let i = mid - 1; i >= lo; i--) {          // grow leftwards from mid - 1: every suffix of the left half
      sum += nums[i];
      leftBest = Math.max(leftBest, sum);
    }
    sum = 0;
    let rightBest = -Infinity;
    for (let j = mid; j < hi; j++) {               // grow rightwards from mid: every prefix of the right half
      sum += nums[j];
      rightBest = Math.max(rightBest, sum);
    }
    return Math.max(best(lo, mid), best(mid, hi), leftBest + rightBest);
  }
  return best(0, nums.length);
}
// maxSubarrayDC([-2, 1, -3, 4, -1, 2, 1, -5, 4]) → 6

Dry run: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The ranges below are listed in the order they finish, which is bottom-up. The crossing sum is leftBest + rightBest, the best subarray that uses both neighbours of mid.

At the top, the left half's best is 4 and the right half's best is 4, but the crossing subarray [4, -1, 2, 1] has sum 6. Scanning left from index 3 gives suffix sums 4, 1, 2, 0, so the best is 4 (just [4]); scanning right from index 4 gives prefix sums -1, 1, 2, -3, 1, so the best is 2 ([-1, 2, 1]). Neither half could have found 6 alone.

Cost. The two scans cost n per range and the recursion has two calls, so T(n) = 2T(n/2) + n, which is O(n log n) time with O(log n) recursion depth and no extra arrays. That is slower than the one-pass answer, and it is the honest reason Kadane's algorithm wins the usual interview question: it needs O(n) time and O(1) space and a few lines (arrays and strings). Offer the divide-and-conquer solution only when the interviewer asks for it, or when the problem changes shape, as the next version shows.

A better combine. The crossing scans exist only because the halves returned a single number. Let each range return four, so that the combine becomes O(1):

function maxSubarraySummary(nums) {
  if (nums.length === 0) throw new RangeError("needs at least one element");
  function summarize(lo, hi) {
    if (hi - lo === 1) {
      const v = nums[lo];
      return { total: v, prefix: v, suffix: v, best: v };
    }
    const mid = lo + ((hi - lo) >> 1);
    const left = summarize(lo, mid);
    const right = summarize(mid, hi);
    return {
      total: left.total + right.total,                                 // the whole range summed
      prefix: Math.max(left.prefix, left.total + right.prefix),         // best sum of a prefix: stop in the left, or take all of the left and go on
      suffix: Math.max(right.suffix, right.total + left.suffix),        // best sum of a suffix, by symmetry
      best: Math.max(left.best, right.best, left.suffix + right.prefix), // inside a half, or across the middle
    };
  }
  return summarize(0, nums.length).best;
}

Now the recurrence is T(n) = 2T(n/2) + 1, which solves to O(n): the same asymptotic cost as Kadane, with O(log n) recursion depth but an object allocated per call. It is not a faster way to answer one query. What it buys is a mergeable summary: the four numbers for a range can be combined with the four numbers of its neighbour in O(1), which is exactly the node of a segment tree that answers "maximum subarray inside positions l to r" with updates (the struct nodes in segment and Fenwick trees). It also suits data that arrives already cut into chunks on different machines: each chunk sends four numbers.

Count of smaller numbers after self

Given nums, return an array counts where counts[i] is the number of elements to the right of position i that are strictly smaller than nums[i]. For [5, 2, 6, 1] the answer is [2, 1, 1, 0]. The brute force is two nested loops, O(n²). The sorting chapter counted all inversions with one number; here every element needs its own count, and the same merge-sort skeleton gives it with one change: the recursion must remember whose count is whose.

Sort positions, not values. Keep an array order of indexes, and compare nums[order[i]] when merging, so after the sort you still know the original position of every element. Now take the merge of a sorted left half and a sorted right half. When the merge writes a left element x, the right elements already written are exactly the right elements that are smaller than x (if ties are taken from the left first, strictly smaller). They sit to the right of x in the original array, because the whole right half does. So add the number of right elements written so far to x's count. Every pair (i, j) with i before j is split at exactly one level, the one where i is in the left half and j in the right, and is counted there; a pair is never seen twice, so the counts simply accumulate with += as the recursion unwinds.

function countSmaller(nums) {
  const n = nums.length;
  const counts = new Array(n).fill(0);
  const order = Array.from({ length: n }, (_, i) => i);   // order[k] is the original position of the element now at slot k
  const aux = new Array(n);

  function sort(lo, hi) {                              // sorts order[lo, hi) by value, adding to counts as it merges
    if (hi - lo <= 1) return;
    const mid = lo + ((hi - lo) >> 1);
    sort(lo, mid);
    sort(mid, hi);
    let i = lo, j = mid;
    for (let k = lo; k < hi; k++) {
      if (j === hi || (i < mid && nums[order[i]] <= nums[order[j]])) {
        counts[order[i]] += j - mid;                   // right elements already written are all smaller than this one
        aux[k] = order[i++];
      } else {
        aux[k] = order[j++];
      }
    }
    for (let k = lo; k < hi; k++) order[k] = aux[k];
  }

  sort(0, n);
  return counts;
}
// countSmaller([5, 2, 6, 1]) → [2, 1, 1, 0]

Dry run: countSmaller([5, 2, 6, 1])

The element 5 gains 1 in the first merge (it jumped over 2) and 1 in the last (it jumped over 1), for a total of 2: the two smaller values to its right. The 6 gains 1 from the element 1 and nothing more, since 5 and 2 are on its left, and the 1 has nothing to its right. Time is O(n log n), as for any merge sort that adds O(1) per written element; extra space is O(n) for order, aux and counts. A Fenwick tree over compressed values gives the same bound with a different tool (segment and Fenwick trees); merge sort needs no coordinate compression and touches the data in sorted runs.

Count of range sum

Count the pairs (i, j) with i < j (a non-empty subarray nums[i..j-1]) whose sum lies between lower and upper, both inclusive. For [-2, 5, -1] with the range [-2, 2] the subarrays are -2, 5, -1, 3, 4 and 2, and three of them (-2, -1 and 2) qualify. The brute force is O(n²).

Turn sums into differences. Let P be the prefix sums with a leading 0, so P[0] = 0 and P[k] = nums[0] + … + nums[k-1]. The sum of nums[i..j-1] is P[j] − P[i], so the task is: count the index pairs i < j among the n + 1 prefix values with lower ≤ P[j] − P[i] ≤ upper. That has the shape of the inversion problem, and the same attack works. Split the prefix array in the middle. Pairs inside a half are the recursion's job. For the pairs with i in the left half and j in the right half, the positions no longer matter: every left index is before every right index, however the halves are ordered inside. So once both halves are sorted, for each left value P[i] the matching right values form a contiguous run: those with P[i] + lower ≤ P[j] ≤ P[i] + upper. As P[i] increases, both ends of that run move right, never left, so two pointers find every run in one pass.

function countRangeSum(nums, lower, upper) {
  const prefix = [0];
  for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);   // n + 1 prefix sums, starting with 0
  const aux = new Array(prefix.length);

  function sortCount(lo, hi) {                         // sorts prefix[lo, hi), returns the qualifying pairs inside it
    if (hi - lo <= 1) return 0;
    const mid = lo + ((hi - lo) >> 1);
    let count = sortCount(lo, mid) + sortCount(mid, hi);
    let from = mid, to = mid;                          // the run of right values for the current left value is [from, to)
    for (let i = lo; i < mid; i++) {
      while (from < hi && prefix[from] - prefix[i] < lower) from++;    // too small: P[j] - P[i] below lower
      while (to < hi && prefix[to] - prefix[i] <= upper) to++;       // still within upper
      count += to - from;
    }
    let i = lo, j = mid;                               // now the ordinary merge
    for (let k = lo; k < hi; k++) {
      aux[k] = j === hi || (i < mid && prefix[i] <= prefix[j]) ? prefix[i++] : prefix[j++];
    }
    for (let k = lo; k < hi; k++) prefix[k] = aux[k];
    return count;
  }

  return sortCount(0, prefix.length);
}
// countRangeSum([-2, 5, -1], -2, 2) → 3

Dry run: countRangeSum([-2, 5, -1], -2, 2)

The prefix sums are [0, -2, 3, 2]. The recursion splits them into [0, -2] and [3, 2]. In the first half the only pair is (0, -2) with difference -2, in range: 1. In the second half the pair is (3, 2) with difference -1: 1. Both halves are then sorted to [-2, 0] and [2, 3], and the top-level counting runs:

The cross pairs add 1, for a total of 1 + 1 + 1 = 3, matching the three qualifying subarrays. The pair counted at the top is P[0] = 0 against P[3] = 2: the subarray [-2, 5, -1] itself, whose sum is 2. Time is O(n log n) with O(n) extra space, since the counting pass is linear and the merge is linear at every level. Note that both pointers are set once per merge, before the loop, and are never reset inside it: that is what makes the pass linear.

The counting problems here and in the sorting chapter share one skeleton, and it is worth stating as a rule: if a question is about pairs (i, j) with i before j, and the relation between the two elements is something a sorted order can answer in bulk (smaller than, more than double, within a window), sort by merging and count the cross pairs while the halves are sorted. Inversions, reverse pairs (nums[i] > 2 · nums[j]), smaller-after-self and range-sum counts differ only in the counting pass. A Fenwick tree over compressed values is the other standard tool for these counts, and segment and Fenwick trees solves two of them that way.

The skyline problem: merge two outlines

Each building is [left, right, height]. The skyline is the outline you see from far away, reported as the points where the height changes: [x, height] means "from x onwards, the height is height", and the last point has height 0. For [[2, 9, 10], [3, 7, 15], [5, 12, 12]] the answer is [[2, 10], [3, 15], [7, 12], [12, 0]]. Coordinates can be huge, so you cannot walk every x; the height only changes at building edges, and that is where all the work is.

The skyline of one building is trivial: [[left, height], [right, 0]]. Now the combine: given the skylines of two halves of the buildings, produce the skyline of all of them. The outline of a union of buildings is the pointwise maximum of the outlines. Each outline is a step function that holds its height from one key point to the next, so sweep both lists left to right, like merging two sorted lists. Keep the current height of each outline. At every x where either list has a key point, update that outline's height, take the larger of the two, and emit a key point if the result differs from the last height emitted.

function mergeSkylines(a, b) {
  const out = [];
  let i = 0, j = 0, heightA = 0, heightB = 0;
  while (i < a.length || j < b.length) {
    const x = Math.min(i < a.length ? a[i][0] : Infinity, j < b.length ? b[j][0] : Infinity);
    if (i < a.length && a[i][0] === x) heightA = a[i++][1];          // a has a key point here: its height changes
    if (j < b.length && b[j][0] === x) heightB = b[j++][1];          // b may have one at the same x: take both
    const height = Math.max(heightA, heightB);
    if (out.length === 0 ? height !== 0 : height !== out[out.length - 1][1]) out.push([x, height]);
  }
  return out;
}

function getSkyline(buildings) {
  function build(lo, hi) {
    if (hi - lo === 0) return [];
    if (hi - lo === 1) {
      const [left, right, height] = buildings[lo];
      return [[left, height], [right, 0]];
    }
    const mid = lo + ((hi - lo) >> 1);
    return mergeSkylines(build(lo, mid), build(mid, hi));
  }
  return build(0, buildings.length);
}
// getSkyline([[2, 9, 10], [3, 7, 15], [5, 12, 12]]) → [[2, 10], [3, 15], [7, 12], [12, 0]]

Dry run: mergeSkylines([[2, 10], [9, 0]], [[3, 15], [7, 0]])

This merges the outlines of two single buildings, [2, 9, 10] and [3, 7, 15], the first two of the example above.

The result is [[2, 10], [3, 15], [7, 10], [9, 0]]. Merging in the outline of the third building, [[5, 12], [12, 0]], keeps [3, 15] (the 15 is taller), turns [7, 10] into [7, 12] (the third building is taller than the first from x = 7), drops [9, 0] (the height stays 12 there) and ends at [12, 0], which gives the answer above. Time is T(n) = 2T(n/2) + n, which is O(n log n): the number of key points in a merged skyline is at most the number in the two inputs, so each merge is linear. The heap-based sweep line is the other standard solution and reaches the same bound (see Meeting Rooms II in intervals and the skyline in the later sweep-line chapter); the merge version is the one that needs no priority queue and generalizes to merging outlines of any step function.

Closest pair of points

Given n points in the plane, find the smallest distance between any two. Checking every pair is O(n²). Sort by x and cut at the middle point. The closest pair is either inside the left half, inside the right half, or has one point on each side. The recursion gives the first two; call the smaller of those two distances d. For the third case, a pair that beats d must have both of its points within d of the dividing line, so only the points in a vertical strip of width 2d around it can take part.

A strip can still hold all n points, so comparing every pair inside it would be quadratic. The fix is an ordering and a packing argument. Sort the strip's points by y, and for each point look only at the earlier strip points whose y is less than d below it. Those points all fit in a box of width 2d and height d. Cut that box into eight squares of side d/2. Each square lies on one side of the dividing line, and two points on the same side are at least d apart, because that side's closest pair is at least d; but a square of side d/2 has diagonal d/√2, which is less than d. So each square holds at most one point, the box holds at most 8, and the current point has at most 7 earlier neighbours to check. (Points lying exactly on the line make the counting fiddlier, but the conclusion, a small constant, stands.) The strip costs O(n) once it is sorted by y.

Sorting the strip at every level would cost O(n log n) per level and give O(n log² n) overall (the third trap from the recurrence section). Instead, let the recursion return its points sorted by y, by merging the two halves exactly as merge sort does, so that the strip is read off in y-order for free.

function closestPairSquared(points) {                 // squared distance of the closest pair; Infinity for fewer than 2 points
  const n = points.length;
  if (n < 2) return Infinity;
  const pts = points.slice().sort((p, q) => p[0] - q[0]);   // sorted by x; the caller's array is untouched
  const aux = new Array(n);
  const strip = new Array(n);
  const dist2 = (p, q) => (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2;

  function solve(lo, hi) {                             // closest squared distance inside pts[lo, hi); leaves that range sorted by y
    if (hi - lo <= 3) {
      let best = Infinity;
      for (let i = lo; i < hi; i++) for (let j = i + 1; j < hi; j++) best = Math.min(best, dist2(pts[i], pts[j]));
      const part = pts.slice(lo, hi).sort((p, q) => p[1] - q[1]);
      for (let k = 0; k < part.length; k++) pts[lo + k] = part[k];
      return best;
    }
    const mid = lo + ((hi - lo) >> 1);
    const midX = pts[mid][0];                          // read before the recursion reorders the range by y
    let best = Math.min(solve(lo, mid), solve(mid, hi));
    let i = lo, j = mid;
    for (let k = lo; k < hi; k++) {                    // merge by y, like merge sort
      aux[k] = j === hi || (i < mid && pts[i][1] <= pts[j][1]) ? pts[i++] : pts[j++];
    }
    for (let k = lo; k < hi; k++) pts[k] = aux[k];
    let size = 0;
    for (let k = lo; k < hi; k++) {
      const p = pts[k];
      if ((p[0] - midX) ** 2 >= best) continue;        // outside the strip
      for (let t = size - 1; t >= 0 && (p[1] - strip[t][1]) ** 2 < best; t--) {
        best = Math.min(best, dist2(p, strip[t]));     // at most 7 iterations, by the packing argument
      }
      strip[size++] = p;
    }
    return best;
  }

  return solve(0, n);
}
// Math.sqrt(closestPairSquared(points)) is the distance itself

Dry run: the top-level combine for eight points

Take the points (0,3) (1,9) (4,7) (6,0) | (7,0) (8,7) (9,10) (10,8), already sorted by x and cut after the fourth. The best squared distance in the left half is 13 (between (1,9) and (4,7)), and in the right half it is 5 (between (9,10) and (10,8)), so the squared d is 5 and midX is 7. The merged order by y is (6,0) (7,0) (0,3) (4,7) (8,7) (10,8) (1,9) (9,10).

The pair (6,0) and (7,0) straddles the line and beats both halves: the answer is a squared distance of 1. Neither half could have seen it. Note that once best drops to 1, the strip shrinks as well, because the test uses the current best.

Cost. T(n) = 2T(n/2) + n (one merge by y plus one strip scan), so O(n log n) time after the initial sort by x, and O(n) extra space. The work uses squared distances: for integer coordinates every comparison is then exact, and no square root is taken until the very end. This is a classic, but interviews rarely ask for the full O(n log n) code; what they listen for is the three-way split of the answer, the strip, and the reason the strip scan is linear.

Different ways to add parentheses

Given an expression such as "2*3-4*5" made of non-negative integers and the operators +, - and *, return the results of every possible way of fully parenthesizing it. Here the combine is a cross product. Pick the last operator to be applied, any of them: it splits the expression into a left sub-expression and a right sub-expression, each of which can be parenthesized in several ways. If the left has results L and the right has results R, then this split contributes one result for every pair (l, r), namely l op r. The answer is the union over all choices of the operator.

function diffWaysToCompute(expression) {
  const tokens = expression.match(/\d+|[-+*]/g);        // numbers sit at even positions, operators at odd ones
  const memo = new Map();

  function apply(op, a, b) {
    if (op === "+") return a + b;
    if (op === "-") return a - b;
    return a * b + 0;                                 // + 0 turns a -0 (from 0 * -3) into 0
  }

  function ways(lo, hi) {                              // every result of tokens[lo..hi], both ends inclusive
    if (lo === hi) return [Number(tokens[lo])];
    const key = lo * tokens.length + hi;
    if (memo.has(key)) return memo.get(key);
    const results = [];
    for (let op = lo + 1; op < hi; op += 2) {          // each operator in turn is the last one applied
      const lefts = ways(lo, op - 1);
      const rights = ways(op + 1, hi);
      for (const a of lefts) for (const b of rights) results.push(apply(tokens[op], a, b));
    }
    memo.set(key, results);
    return results;
  }

  return ways(0, tokens.length - 1);
}
// diffWaysToCompute("2-1-1") → [2, 0]    diffWaysToCompute("2*3-4*5") → [-34, -10, -14, -10, 10]

Dry run: "2*3-4*5"

The tokens are 2 * 3 - 4 * 5. The last applied operator can be the first *, the -, or the second *:

The five results are -34, -10, -14, -10 and 10, in the order the code produces them; two equal -10 because two different parenthesizations give the same value, and the problem keeps both. The same sub-expressions are asked for by more than one split: with more numbers, 3-4*5 is a sub-problem of several larger ones, and that is why the code has a memo keyed by the pair (lo, hi).

Cost. The number of results is the Catalan number for the count of operators: 1, 2, 5, 14, 42, 132, 429, 1,430 and 4,862 results for expressions with 1 to 9 operators, and 16,796 for 10. No algorithm that returns every result can beat the output size, so time and space grow exponentially, and an interviewer will give a short expression for that reason. The memo does not change that, but it does remove repeated work: for ten numbers joined with + (nine operators) it cuts the recursive calls from 19,683 to 331 and the pair-combining operations from 26,928 to 9,891, against the 4,862 values the answer itself holds. This is the one problem in the chapter where the subproblems overlap; divide and conquer with a cache is the bridge to dynamic programming.

Majority element by splitting

Find the value that appears more than n/2 times in an array, or report that there is none. The one-pass Boyer-Moore vote and a counting map both solve it (arrays and strings), and either is better in practice. The divide-and-conquer version is a small, clean example of a combine that verifies instead of computes.

The key fact: if a value is a strict majority of a range, it is a strict majority of at least one of the two halves. If it were at most half of each, it would be at most half of the whole. So each half can hand up a single candidate, the only value that could be its majority (or "none"). To combine: if both halves name the same candidate, it has a majority in each half and therefore in the whole. If they name different ones, count each in the whole range and keep the one whose count exceeds half the range, if any.

const NONE = Symbol("no majority");

function findMajority(nums) {                          // the value that appears more than n / 2 times, or null
  function count(value, lo, hi) {
    let c = 0;
    for (let i = lo; i < hi; i++) if (nums[i] === value) c++;
    return c;
  }

  function candidate(lo, hi) {                         // the only value that could be a strict majority of [lo, hi), or NONE
    if (hi - lo === 1) return nums[lo];
    const mid = lo + ((hi - lo) >> 1);
    const left = candidate(lo, mid);
    const right = candidate(mid, hi);
    if (left === right) return left;                   // a strict majority of both halves is one of the whole range
    const need = (hi - lo) >> 1;                      // a strict majority needs more than floor(length / 2)
    if (left !== NONE && count(left, lo, hi) > need) return left;
    if (right !== NONE && count(right, lo, hi) > need) return right;
    return NONE;
  }

  if (nums.length === 0) return null;
  const found = candidate(0, nums.length);
  return found === NONE ? null : found;
}
// findMajority([2, 2, 1, 1, 1, 2, 2]) → 2    findMajority([1, 2, 1]) → 1    findMajority([1, 1, 2, 2]) → null

Dry run: [2, 2, 1, 1, 1, 2, 2]

Each level does at most two counting passes over its range, so T(n) = 2T(n/2) + n and the total is O(n log n) time with O(log n) stack; the vote needs O(n) and O(1), and a counting map O(n) with O(n) space. Two details are worth the care. The threshold is floor(length / 2) and the test is strictly greater: for an even length like [1, 1, 2, 2] a value appearing exactly half the time is not a majority. And "no candidate" needs a value that no input can equal (a Symbol here), not -1 or undefined, which can be legitimate array contents.

pow(x, n): a split with one subproblem

Computing xⁿ with n multiplications is O(n). The split xⁿ = (x^⌊n/2⌋)² · (x if n is odd) has a = 1 sub-call on half the exponent and a combine of one or two multiplications, so T(n) = T(n/2) + 1, which is O(log n): the first row of the recurrence table above. The recursion chapter derived this and showed the one-character mistake that undoes it (calling the half twice, which is a = 2 and O(n)). What the interview version adds is the edge cases, so here is the form to write:

function myPow(x, n) {
  if (n < 0) return myPow(1 / x, -n);               // x to a negative power is (1/x) to the positive one
  if (n === 0) return 1;
  const half = myPow(x, Math.floor(n / 2));            // ONE call, result reused
  return n % 2 === 0 ? half * half : half * half * x;
}
// myPow(2, 10) → 1024    myPow(2, -2) → 0.25    myPow(0, -1) → Infinity    myPow(2, -2147483648) → 0

Dry run: myPow(2, -3)

Edge cases checked against Math.pow on thousands of random bases and exponents: n = 0 gives 1 for every x, including 0; x = 0 with a negative n gives Infinity (the inverted base 1/0 is Infinity); the most negative 32-bit exponent -2147483648 works because -n is an ordinary double in JavaScript (a language with 32-bit integers would overflow negating it, and needs a wider type); a huge result overflows to Infinity and a tiny one underflows to 0. Compare floating-point results with a tolerance, not ===: squaring multiplies in a different order from the loop, so the last digits differ.

Median of two sorted arrays as a k-th element search

Given two sorted arrays, find the median of all their elements together, in time better than the O(m + n) merge. The binary-search chapter solves it by searching for the cut position in the shorter array. Here is the same problem seen as divide and conquer, which many people find easier to get right: the median is the k-th smallest element of the union (the two middle ones, if the total is even), and you can find the k-th by throwing away a block of elements that provably cannot be it.

Let h = ⌊k/2⌋. Compare the h-th remaining element of each array: p = a[i + h − 1] and q = b[j + h − 1], where i and j count what has been discarded so far, and suppose p ≤ q (the other case is symmetric). Count the elements that sort before p in the union, with ties going to a first. In a there are h − 1. In b there are only elements smaller than p, and since q ≥ p those are among the first h − 1 of b. So at most 2h − 2 elements come before p, p sits at position 2h − 1 or earlier, and 2h − 1 ≤ k − 1. That means p, and every element of a before p, is among the k − 1 smallest and cannot be the k-th. Discard those h elements, reduce k by h, and repeat. The problem shrinks by a constant fraction every step and there is no combine at all: T(k) = T(k/2) + 1, so O(log k).

function kthOfTwoSorted(a, b, k) {                      // k-th smallest (1-based) of the union; 1 <= k <= a.length + b.length
  let i = 0, j = 0;                                   // a[0, i) and b[0, j) have been discarded
  while (true) {
    if (i === a.length) return b[j + k - 1];          // a is used up: the answer is in b
    if (j === b.length) return a[i + k - 1];
    if (k === 1) return Math.min(a[i], b[j]);
    const step = k >> 1;
    const nextI = Math.min(i + step, a.length);        // a short array offers all it has
    const nextJ = Math.min(j + step, b.length);
    if (a[nextI - 1] <= b[nextJ - 1]) {
      k -= nextI - i;                                 // discard what a offered, and count what was actually discarded
      i = nextI;
    } else {
      k -= nextJ - j;
      j = nextJ;
    }
  }
}

function medianOfTwoSorted(a, b) {
  const total = a.length + b.length;
  if (total === 0) return NaN;
  const mid = total >> 1;
  if (total % 2 === 1) return kthOfTwoSorted(a, b, mid + 1);
  return (kthOfTwoSorted(a, b, mid) + kthOfTwoSorted(a, b, mid + 1)) / 2;
}
// medianOfTwoSorted([1, 3], [2]) → 2    medianOfTwoSorted([1, 2], [3, 4]) → 2.5

Dry run: the 7th smallest of [1, 4, 7, 10, 13] and [2, 3, 5, 6, 8, 9, 11, 12]

The merged order is 1 through 13, so the 7th is 7. Time is O(log(m + n)) for one k-th (two calls for an even total) and space is O(1). The partition search in the binary-search chapter is O(log min(m, n)), slightly tighter, and a little harder to keep straight; either answer is accepted, and this one is a good fallback because its invariant is just "everything discarded is below the k-th".

Split on the elements that cannot be in the answer

Not every split is "cut in the middle". Find the length of the longest substring of s in which every character appears at least k times. A character that appears fewer than k times in the whole string cannot be in any valid substring, because a substring has at most as many copies as the string. So any answer lies strictly between two occurrences of such a character, and the string can be split at every one of them, and the pieces solved independently. If a piece has no such character, the piece itself is valid, and is the best the piece can offer.

function longestSubstring(s, k) {
  function solve(lo, hi) {                            // longest valid substring of s[lo, hi)
    if (hi - lo < k) return 0;
    const count = new Map();
    for (let i = lo; i < hi; i++) count.set(s[i], (count.get(s[i]) ?? 0) + 1);
    let best = 0, start = lo, split = false;
    for (let i = lo; i < hi; i++) {
      if (count.get(s[i]) < k) {                      // this character cannot be in any valid substring of this range
        split = true;
        best = Math.max(best, solve(start, i));       // the piece before it
        start = i + 1;
      }
    }
    if (!split) return hi - lo;                       // every character is frequent: the whole range is valid
    return Math.max(best, solve(start, hi));          // the last piece
  }
  return solve(0, s.length);
}
// longestSubstring("ababbc", 2) → 5    longestSubstring("aaabbcbbbb", 3) → 4

Dry run: longestSubstring("aaabbcbbbb", 3)

The answer is 4. The pieces are different sizes, so this does not fit the T(n/b) form, but the depth is bounded in a different way: every piece lacks at least one distinct character that its parent had (all copies of the rare character were removed). With an alphabet of size σ the recursion is at most σ deep, each level does O(n) work in total because the pieces do not overlap, and the running time is O(σ · n), which is O(26 n) for lowercase letters. Space is O(σ²) at worst, for the count maps on the current recursion path.

Karatsuba and Strassen: the recurrence is the story

Two famous results are worth knowing at the level of the recurrence, not the code. Multiplying two n-digit numbers the way you learned at school takes n² digit multiplications. Split each number into a high and low half, x = x₁ · B + x₀ and y = y₁ · B + y₀, where B is the base raised to half the digits. Then x · y = x₁y₁ · B² + (x₁y₀ + x₀y₁) · B + x₀y₀, which is four half-size products: T(n) = 4T(n/2) + n, so r = 4/2 = 2 and the total is n^{log₂ 4} = n². The split alone buys nothing. Karatsuba's observation is that the middle coefficient does not need two products: x₁y₀ + x₀y₁ = (x₁ + x₀)(y₁ + y₀) − x₁y₁ − x₀y₀, and both subtracted products are already computed. Three half-size products instead of four give T(n) = 3T(n/2) + n, and r = 3/2, so the total is n^{log₂ 3}, about n^1.585.

A check by hand, with B = 100: for 1234 × 5678 take x₁ = 12, x₀ = 34, y₁ = 56, y₀ = 78. The high product is 12 · 56 = 672, the low product is 34 · 78 = 2,652, and the middle is (12 + 34)(56 + 78) − 672 − 2,652 = 6,164 − 3,324 = 2,840. Then 672 · 10,000 + 2,840 · 100 + 2,652 = 7,006,652, which is 1234 × 5678.

Strassen's algorithm does the same for matrices: splitting each into four blocks, the schoolbook method needs eight half-size block multiplications, T(n) = 8T(n/2) + n², which is n³. Strassen found seven products, from which the four result blocks follow by additions, so T(n) = 7T(n/2) + n², which is O(n^{log₂ 7}), about n^2.807. In both cases the combine is cheap additions, and the whole gain is lowering a by one: the lesson to take is that for a divide and conquer, the number of recursive calls matters more than the cost of the split and the combine once the recursion is deep. Neither is something to write in an interview; the constants make the schoolbook method faster for small inputs, and each is usually named as the example of the idea.

Parallelism and caches, honestly

Two arguments for divide and conquer are repeated often, and both are true in a limited way. First, the halves are independent, so in principle they can run at the same time on different cores or machines. But the combine runs after both halves finish, and with a sequential merge the merge at the top alone takes time proportional to n, so merge sort does not speed up by a factor of the number of cores; a parallel merge is a separate, harder algorithm. Second, recursion works on smaller and smaller ranges, and once a range is small enough to sit in a processor cache, the work below it can run on cached data. That is the idea behind cache-oblivious algorithms, and one motivation for recursive and blocked formulations of numeric routines. Neither argument is a promise for your code: JavaScript runs your functions on one thread, workers cannot share ordinary objects (only the bytes of a SharedArrayBuffer), and this chapter's code has not been timed for either effect. In an interview, one sentence is enough: "the halves are independent, so it parallelizes and distributes naturally, and the combine is the sequential part."

When divide and conquer loses

The split is a tool, not a goal. Reach for something else when:

Two further cautions. The recursion depth is only O(log n) when the split is balanced; with an unbalanced one, a deep recursion can overflow the stack long before it runs out of time (the recursion chapter measures the limit). And a divide-and-conquer answer can be right and still lose points if a one-line scan exists: say the simple solution first, then offer the split.

The mistakes that cost points

Recognizing it in an unseen problem

• The problem is about pairs in the wrong order, or pairs whose values satisfy a relation, and the brute force is O(n²): merge sort that counts while merging (smaller after self, range-sum counts, reverse pairs, inversions).
• The answer is the best of "inside the left", "inside the right" and "across the middle": a crossing scan or a mergeable summary (maximum subarray, closest pair).
• The answer is built from two sub-answers of the same kind: merging outlines or sorted lists (skyline, merge k sorted lists by halving, in the practice list), or a cross product of results (parentheses).
• The word every ("all possible results"): the output is the cross product of the halves; expect exponential output and ask about the size limit.
• A property that must hold for a candidate in each half if it holds for the whole (a strict majority is a majority of one half): hand up a candidate, then verify.
• An element or a character that cannot belong to any answer: split on it and solve the pieces.
• A sorted structure and a question about the k-th or the median: discard a block that cannot hold the answer, so the problem shrinks without a combine.
• The constraint is n up to 10⁵ and the brute force is quadratic, but the data has no obvious order: an n log n divide and conquer is the usual target (see the constraints table in the complexity chapter).
• Distinguish it from dynamic programming (overlapping subproblems), from greedy (one choice at a time, no sub-answers to combine) and from backtracking (explore and undo choices rather than split the data).