Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Median of Two Sorted Arrays

Searchinghard

Given two sorted arrays `a` and `b`, implement `findMedianSortedArrays(a, b)` returning the median of the combined set. Aim for O(log(min(m, n))).

Examples

Input: a = [1, 3], b = [2]
Output: 2
Merged: [1, 2, 3], median 2.
Input: a = [1, 2], b = [3, 4]
Output: 2.5
Merged: [1, 2, 3, 4], median (2+3)/2.

Sample tests

Input: findMedianSortedArrays([1,3], [2])
Output: 2
Input: findMedianSortedArrays([1,2], [3,4])
Output: 2.5

+ 2 hidden tests run on Submit.

Hints

Common pitfalls
  • Always binary-search the smaller array, or the partition index can go out of range.
  • Use ±Infinity sentinels for empty partition sides to avoid special-casing the edges.

Learning resources

  • Wikipedia: Binary search algorithm
Approach & explanation (try first)

Partition the two arrays so the combined left half has ⌈(m+n)/2⌉ elements. The partition is valid when the largest left element does not exceed the smallest right element on the opposite side. Binary searching the smaller array for that cut runs in O(log(min(m, n))).

Loading...
⌘/Ctrl + Enter

Run your code to see results.