Partition two sorted arrays

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Two sorted lists: A = 1, 3, 8, 9, 15 and B = 7, 11, 18, 19, 21, 25. Eleven numbers in total; the median is the 6th smallest. By hand you merge them: 1, 3, 7, 8, 9, 11, … and the 6th is 11. Merging costs about 11 looks, and for two lists of a million each it costs a million looks, even though we only want one number.

Think about what the median does. It splits the eleven numbers into a left group of 5 (the smaller ones) and a right group of 6. Every number in the left group is ≤ every number in the right group. The left group takes some numbers from the front of A and the rest from the front of B. If it takes i from A it must take 5 − i from B. So the whole question is: what is i?

Build the structure, one piece at a time

Piece 1: a cut in each list. Choose i, the number of elements of A on the left. Then j = 5 − i elements of B go on the left. Four numbers matter: A's last left element A[i − 1], A's first right element A[i], and the same two for B.

Piece 2: a test for the cut. The cut is right when both left pieces are below both right pieces: A[i − 1] ≤ B[j] and B[j − 1] ≤ A[i]. (Within each list the order is automatic because the lists are sorted.)

Piece 3: which way to move. If B[j − 1] > A[i], B is giving too much to the left, so A should give more: increase i. If A[i − 1] > B[j], decrease i. Because moving i by one shifts exactly one number across the cut, this is a monotone condition, and we binary search i over 0 to 5.

The left group is {1, 3, 8, 9} from A and {7} from B, five numbers, all ≤ every right number. With an odd total the median is the smallest right number: min(15, 11) = 11. With an even total it is the average of the largest left and smallest right.

Why it is correct

The invariant of the search: the correct i lies in [lo, hi].

Why is the test monotone? Define bad(i) as "B[j − 1] > A[i]", meaning i is too small. Increasing i by one raises A[i] (A is sorted) and lowers j, which lowers B[j − 1]. So once bad(i) becomes false it stays false. The smallest i with bad false is the answer, and the standard boundary search finds it. At that i, the other inequality A[i − 1] ≤ B[j] also holds, otherwise i − 1 would have been a valid cut too, contradicting minimality.

left = {A[0..i−1]} ∪ {B[0..j−1]}, |left| = ⌊(m + n + 1) / 2⌋, max(left) ≤ min(right)

Edge cases: when i = 0 there is no A-left element, treat it as −∞; when i = m there is no A-right element, treat it as +∞. Same for B.

Why it is fast

The search runs over i from 0 to the length of the shorter list, and each probe does four lookups.

time = O(log min(m, n)), versus O(m + n) for merging

Two lists of a million each: about 20 probes instead of a million looks.

How to recognise it in an interview

The cues are "median of two sorted arrays", "kth smallest across two sorted arrays", or the demand for logarithmic time on two sorted inputs. Say: "I binary search how many elements the first array contributes to the left half; the cut is correct when both left maxima are below both right minima."

Median of Two Sorted Arrays is the example above. Kth Smallest Element in a Sorted Matrix is a cousin: binary search over the value and count how many entries are ≤ it. Find K-th Smallest Pair Distance does the same over distances.

02The idea in one line

Binary search the cut in the shorter array so left halves hold exactly half the items.

Reach for it when: Median of two sorted arrays, kth element of two arrays.

Cost: O(log min(n,m)) time.

03The walk-through, step by step

The video works one example: Median of [1,3,8,9,15] and [7,11,18,19,21,25]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Binary search the cut in A so the left halves hold half the items
2. Try i = 2, j = 6 − 2 = 4: left maxes 3, 19 · right mins 8, 21
3. B's left max 19 > A's right min 8: move the cut right, lo = 3
4. Try i = 4, j = 6 − 4 = 2: left maxes 9, 11 · right mins 15, 18
5. Every left ≤ every right: the cut is right, median = max(left) = 11
6. Only the shorter array is searched: O(log min(m, n))

04Asked at Google

3 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search: Classic binary search, First true (predicate boundary), Binary search on the answer, Rotated / mountain search.