004. Median of Two Sorted Arrays

At a Glance

Topic: binary-search
Pattern: Binary Search (partition the two arrays)
Difficulty: Hard
Companies: Google, Amazon, Microsoft, Apple, Meta
Frequency: High
LeetCode: 4

Problem (one-liner)

Given two sorted arrays leftSorted and rightSorted, return the median of the merged multiset (even length → average of two middle values).

Recognition Cues

Median of two sorted streams without full merge
O(log(min(m,n))) expected — partition not element hunt
Compare four neighbors around cut: maxLeftA <= minRightB and symmetric

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — materialize merged sorted array — O(m+n) time / O(m+n) space.
Acceptable — merge with two pointers until (m+n)/2 steps — O(m+n) time / O(1) extra; often enough if interviewer caps follow-ups.
Optimal — partition shorter array so left halves contain ⌊(m+n+1)/2⌋ elements and boundary inequalities hold — O(log(min(m,n))) time / O(1) space; heavy invariant but expected at Hard tier.

Optimal Solution

Go

import "math"

func findMedianSortedArrays(leftSorted []int, rightSorted []int) float64 {
	if len(leftSorted) > len(rightSorted) {
		return findMedianSortedArrays(rightSorted, leftSorted)
	}
	m := len(leftSorted)
	n := len(rightSorted)
	leftHalfCount := (m + n + 1) / 2
	low, high := 0, m
	for low <= high {
		partitionLeft := low + (high-low)/2
		partitionRight := leftHalfCount - partitionLeft
		var maxLeftA, minRightA int
		if partitionLeft == 0 {
			maxLeftA = math.MinInt64
		} else {
			maxLeftA = leftSorted[partitionLeft-1]
		}
		if partitionLeft == m {
			minRightA = math.MaxInt64
		} else {
			minRightA = leftSorted[partitionLeft]
		}
		var maxLeftB, minRightB int
		if partitionRight == 0 {
			maxLeftB = math.MinInt64
		} else {
			maxLeftB = rightSorted[partitionRight-1]
		}
		if partitionRight == n {
			minRightB = math.MaxInt64
		} else {
			minRightB = rightSorted[partitionRight]
		}
		if maxLeftA <= minRightB && maxLeftB <= minRightA {
			if (m+n)%2 == 0 {
				leftMax := maxLeftA
				if maxLeftB > leftMax {
					leftMax = maxLeftB
				}
				rightMin := minRightA
				if minRightB < rightMin {
					rightMin = minRightB
				}
				return float64(leftMax+rightMin) / 2.0
			}
			leftMax := maxLeftA
			if maxLeftB > leftMax {
				leftMax = maxLeftB
			}
			return float64(leftMax)
		}
		if maxLeftA > minRightB {
			high = partitionLeft - 1
		} else {
			low = partitionLeft + 1
		}
	}
	return 0
}

JavaScript

function findMedianSortedArrays(leftSorted, rightSorted) {
	if (leftSorted.length > rightSorted.length) {
		return findMedianSortedArrays(rightSorted, leftSorted);
	}
	const m = leftSorted.length;
	const n = rightSorted.length;
	const leftHalfCount = Math.floor((m + n + 1) / 2);
	let low = 0;
	let high = m;
	while (low <= high) {
		const partitionLeft = Math.floor(low + (high - low) / 2);
		const partitionRight = leftHalfCount - partitionLeft;
		const maxLeftA =
			partitionLeft === 0 ? -Infinity : leftSorted[partitionLeft - 1];
		const minRightA =
			partitionLeft === m ? Infinity : leftSorted[partitionLeft];
		const maxLeftB =
			partitionRight === 0 ? -Infinity : rightSorted[partitionRight - 1];
		const minRightB =
			partitionRight === n ? Infinity : rightSorted[partitionRight];
		if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
			if ((m + n) % 2 === 0) {
				return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
			}
			return Math.max(maxLeftA, maxLeftB);
		}
		if (maxLeftA > minRightB) {
			high = partitionLeft - 1;
		} else {
			low = partitionLeft + 1;
		}
	}
	return 0;
}

Walkthrough

leftSorted = [1,3], rightSorted = [2] → merged [1,2,3], median 2.

Binary search where to cut leftSorted so left side has 2 elements total ((3+1)/2). Try partition after 1 → left [1], right [3] vs [2] → wrong order at boundary; adjust.

Invariant: left partition holds exactly leftHalfCount elements; correctness is purely local via four neighbors.

Edge Cases

One array empty — median is middle of the other
All values equal
Total length 1 or 2
Duplicates everywhere

Pitfalls

Binary searching value instead of partition size
Wrong shorter/longer array — always BS on shorter to guarantee O(log min)
Go: use math.MinInt64 / MaxInt64 for sentinels

Variants

K-th smallest in two sorted arrays — generalize partition target count.
Median of k sorted arrays — heap / divide-and-conquer multi-way merge tradeoffs.
Weighted median — different objective; not partition-friendly.

Mind-Map Tags

#binary-search #partition #median #two-arrays #log-min #sentinel