Hints — p35 Median of Two Sorted Arrays

Read one at a time. This problem is Hard — take your time.

Hint 1 — Brute first. Two-pointer merge, stop at the median index. O(m+n). State it. Then the interviewer will ask for O(log).

Hint 2 — Don’t binary-search a value — binary-search a partition. Imagine splitting the combined sorted array into LEFT and RIGHT halves. The median is determined by the boundary. We choose i elements from A and j elements from B for the left side, with i + j = (T+1)//2. So once i is chosen, j is forced.

Hint 3 — The correctness condition. A partition (i, j) is valid iff:

• A[i-1] <= B[j] (A’s left fits to the left of B’s right)
• B[j-1] <= A[i] (B’s left fits to the left of A’s right)

Use -inf / +inf sentinels for the edge cases (i==0, i==m, j==0, j==n).

Hint 4 — Binary search direction.

• If A[i-1] > B[j] (too many A on left) → shrink i: hi = i - 1.
• Else (too few A on left, so B[j-1] > A[i]) → grow i: lo = i + 1.

Loop while lo <= hi.

Hint 5 — Median formula. Once you find a valid partition:

• Odd total: median = max(maxLeftA, maxLeftB).
• Even total: median = (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2.

ALWAYS binary-search the SMALLER array (swap if needed) — guarantees j stays in [0, n] and gives O(log(min(m, n))).

If still stuck: see solution.py. The function is ~30 lines but every line earns its keep.