Median of Two Sorted Arrays

Hard

Binary Search

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 (m+n)).

Example 1

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints

•nums1.length == m
•nums2.length == n
•0 <= m <= 1000
•0 <= n <= 1000
•1 <= m + n <= 2000
•-10^6 <= nums1[i], nums2[i] <= 10^6

Show Hints (4)

Hint 1: To achieve O(log(m+n)), we need to binary search on the partition position, not merge the arrays.

Hint 2: Binary search on the smaller array to find a partition such that elements on the left are all smaller than elements on the right.

Hint 3: The partition divides both arrays such that left_total = (m + n + 1) / 2 elements are on the left side.

Hint 4: Valid partition: max(left1, left2) <= min(right1, right2). The median is calculated from these boundary elements.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?