Median of Two Sorted Arrays

HARD✓ CHIP-TIMEDLC #4 — FULL STATEMENT ↗

The drill: Two sorted arrays, one combined median — found faster than merging, in log time on the shorter array.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two arrays arrive, each already sorted in its own right but not merged together, and they can differ in length by any amount, including one of them being empty.

Treated as one combined sorted sequence, they have a well-defined median — the middle value if the combined count is odd, or the average of the two middle values if it's even.

The job is to report that median directly, without physically merging the two arrays into one — the faster solution has to reason about how the arrays interleave rather than construct that interleaving.

EX 01

nums1 = [1, 7] · nums2 = [4]

→ 4

EX 02

nums1 = [2, 5] · nums2 = [3, 8]

→ 4

EVEN TOTAL, AVERAGE OF THE MIDDLE TWO

EX 03

nums1 = [] · nums2 = [6]

→ 6

ONE ARRAY EMPTY

arrays combined hold up to a few thousand integers, either can be empty
both input arrays are already sorted in non-decreasing order
answer may be a whole number or carry a fractional half
the two arrays together are never both empty

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A full merge is O(m+n) and already beats concatenate-and-sort. The log target means most elements must never be looked at.

HINT 2 THE STRUCTURE

A median is a partition: a left half and a right half of the combined data. Choose a cut in ONE array and the other array’s cut is forced.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search the cut in the shorter array: if maxLeftA > minRightB move the cut left; if maxLeftB > minRightA move it right. ±∞ sentinels handle the edges.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PARTITION LINEPATTERN · PARTITION SEARCHnums1 = [1, 3, 8] · nums2 = [7, 9, 10, 11]

STEP 1

Two sorted arrays: [1,3,8] and [7,9,10,11] — 7 values combined, median at index 3. Binary-search the partition of the shorter array.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/median-of-two-sorted-arrays.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        a, b = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)
        m, n = len(a), len(b)
        half = (m + n + 1) // 2
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
            a_left = a[i - 1] if i > 0 else float("-inf")
            a_right = a[i] if i < m else float("inf")
            b_left = b[j - 1] if j > 0 else float("-inf")
            b_right = b[j] if j < n else float("inf")
            if a_left > b_right:
                hi = i - 1
            elif b_left > a_right:
                lo = i + 1
            else:
                if (m + n) % 2 == 1:
                    return float(max(a_left, b_left))
                return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
        return 0.0

TIME O(LOG MIN(M,N))SPACE O(1)PYTHON · RACE PACE · 22 LN

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merged = []
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] <= nums2[j]:
                merged.append(nums1[i]); i += 1
            else:
                merged.append(nums2[j]); j += 1
        merged.extend(nums1[i:])
        merged.extend(nums2[j:])
        n = len(merged)
        if n % 2 == 1:
            return float(merged[n // 2])
        return (merged[n // 2 - 1] + merged[n // 2]) / 2.0

TIME O(M+N)SPACE O(M+N)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] a = nums1.length <= nums2.length ? nums1 : nums2;
        int[] b = nums1.length <= nums2.length ? nums2 : nums1;
        int m = a.length;
        int n = b.length;
        int half = (m + n + 1) / 2;
        int lo = 0;
        int hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = half - i;
            int aLeft = i > 0 ? a[i - 1] : Integer.MIN_VALUE;
            int aRight = i < m ? a[i] : Integer.MAX_VALUE;
            int bLeft = j > 0 ? b[j - 1] : Integer.MIN_VALUE;
            int bRight = j < n ? b[j] : Integer.MAX_VALUE;
            if (aLeft > bRight) {
                hi = i - 1;
            } else if (bLeft > aRight) {
                lo = i + 1;
            } else {
                if ((m + n) % 2 == 1) {
                    return Math.max(aLeft, bLeft);
                }
                return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
            }
        }
        return 0.0;
    }
}

TIME O(LOG MIN(M,N))SPACE O(1)JAVA · RACE PACE · 30 LN

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < nums1.length && j < nums2.length) {
            merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < nums1.length) {
            merged[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            merged[k++] = nums2[j++];
        }
        int n = merged.length;
        if (n % 2 == 1) {
            return merged[n / 2];
        }
        return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
    }
}

TIME O(M+N)SPACE O(M+N)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED