⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#4) before relying on it.

🔢 Median of Two Sorted Arrays

An interactive visualization of finding the median of two sorted arrays using binary search on the partition point. Watch the algorithm achieve O(log(min(m,n))) time complexity by partitioning the smaller array.

Binary Search LeetCode 4 ↗ Hard

The Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log(min(m,n))).

Examples:
Input: nums1 = [1,3], nums2 = [2] → Output: 2.0
Input: nums1 = [1,2], nums2 = [3,4] → Output: 2.5

Interactive Visualization

Array 1 (comma-separated)

Array 2 (comma-separated)

Preset

Speed:

Arrays with Partition

Current Step

Press Step or Play to begin.

Code

fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {    var a = nums1; var b = nums2    if (a.size > b.size) {        a = nums2; b = nums1 }    val m = a.size; val n = b.size    var lo = 0; var hi = m    while (lo <= hi) {        val i = (lo + hi) / 2        val j = (m + n + 1) / 2 - i        val maxLeftA = if (i == 0) Int.MIN_VALUE else a[i - 1]        val minRightA = if (i == m) Int.MAX_VALUE else a[i]        val maxLeftB = if (j == 0) Int.MIN_VALUE else b[j - 1]        val minRightB = if (j == n) Int.MAX_VALUE else b[j]        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {            if ((m + n) % 2 == 1)                return maxOf(maxLeftA, maxLeftB).toDouble()            return (maxOf(maxLeftA, maxLeftB) + minOf(minRightA, minRightB)) / 2.0        } else if (maxLeftA > minRightB) {            hi = i - 1        } else {            lo = i + 1        }    }    return 0.0}

def findMedianSortedArrays(nums1, nums2):    A, B = nums1, nums2    if len(A) > len(B):        A, B = B, A    m, n = len(A), len(B)    lo, hi = 0, m    while lo <= hi:        i = (lo + hi) // 2        j = (m + n + 1) // 2 - i        maxLeftA = float('-inf') if i == 0 else A[i - 1]        minRightA = float('inf') if i == m else A[i]        maxLeftB = float('-inf') if j == 0 else B[j - 1]        minRightB = float('inf') if j == n else B[j]        if maxLeftA <= minRightB and maxLeftB <= minRightA:            if (m + n) % 2 == 1:                return max(maxLeftA, maxLeftB)            return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2        elif maxLeftA > minRightB:            hi = i - 1        else:            lo = i + 1

How It Works

Key Insight

Instead of merging the arrays, we use binary search on the partition point of the shorter array. The key idea: if we partition both arrays such that all elements on the left are ≤ all elements on the right, and both halves have equal size (or left has one more), then the median is determined by the boundary elements.

The Algorithm

Ensure A is shorter: Swap if necessary so we binary search on the smaller array (A)
Initialize: lo = 0, hi = len(A)
Binary search: For each partition i in A, compute j = (m+n+1)//2 - i in B
Get boundary values: maxLeftA, minRightA, maxLeftB, minRightB (use -∞ and +∞ for empty partitions)
Check correctness: If maxLeftA ≤ minRightB AND maxLeftB ≤ minRightA, partition is correct
Compute median: If total length is odd, return max(maxLeftA, maxLeftB); if even, return average of max(maxLeftA, maxLeftB) and min(minRightA, minRightB)
Adjust search: If maxLeftA > minRightB, move left (hi = i - 1); otherwise move right (lo = i + 1)

Complexity

Time O(log(min(m,n)))

Space O(1)

Binary search is performed on the shorter array only, giving O(log(min(m,n))) time complexity. Only a constant number of variables are used regardless of input size.