pattern heroPT–23LeetCode Extension

Divide and conquer

Split the problem in half, solve each half the same way and join the two answers. Halving quickly gets down to tiny pieces, so if joining is cheap, the whole thing is much faster than solving it head-on.

Variant
P23 Divide and conquerMerge sort · 1×

Example problem: sort [5, 1, 8, 3, 9, 2] with merge sort.

518392
waiting on the call stackcurrent call or itemsortedmerged list, not filled yetalready merged upwards

sort([5, 1, 8, 3, 9, 2]): 6 items, so split it

a = [5, 1, 8, 3, 9, 2]mid = –left = –right = –out = –
01/62
restart · back · play · step
Speed
1function sort(a):
2 if len(a) <= 1:
3 return a
4 mid = len(a) / 2 // rounded down
5 left = sort(a[0 .. mid - 1])
6 right = sort(a[mid .. len(a) - 1])
7 return merge(left, right)
8
9function merge(left, right):
10 out = []
11 while left and right are not empty:
12 move the smaller first item to out
13 return out + left + right

← → step · space play/pause

How to recognise

the input splits into halves you can solve on their own: sort a list, build a tree from an array or from two traversals, a quad tree, a fast power, merge k sorted lists.

How to solve problems like this

  1. Find a split that leaves pieces of the same kind: two halves of an array, a list cut at its middle, four quadrants.
  2. Write the base case: the smallest piece you can answer at once, often a single item or an empty one.
  3. Solve each piece with a recursive call, and trust the call to return a correct answer.
  4. Write the combine step, and count its cost per level: O(n) per level gives O(n log n) in total.

Variant: Build a tree

The same, but to build a tree: the middle of the sorted array becomes the root and the halves become its subtrees. The halves are the same size, give or take one, so the tree comes out balanced.

  1. Pass index bounds (lo, hi) instead of copying sub-arrays: the split then costs O(1).
  2. The empty range lo > hi is the base case: it returns none.
  3. Pick the piece that splits the rest: the middle of a sorted array, the first value of a preorder for a tree from two traversals.
  4. Make the node, build the left side from one part and the right side from the other, then return the node.

Where it's used

  • Sorting big data. When data does not fit in memory, PostgreSQL sorts it in pieces and then merges the sorted pieces. EXPLAIN shows this as "external merge".
  • Sound and signals. The fast Fourier transform splits a signal into even and odd samples, works out each half the same way and joins the results. FFTW and numpy.fft work this way.
  • Multiplying big numbers. Python multiplies very long integers with Karatsuba's method: it splits each number into two halves and gets by with three multiplications of halves instead of four.