HardBinary SearchAI interview only
Median of Two Sorted Arrays
Asked atgoogleamazonmetaapplemicrosoftgoldman-sachsbloomberg
01 · 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(m + n)).
02 · Examples
Example 01
Input
nums1 = [1,3], nums2 = [2]
Output
2.0
The merged sorted array is [1,2,3]. The median is 2.
Example 02
Input
nums1 = [1,2], nums2 = [3,4]
Output
2.5
The merged sorted array is [1,2,3,4]. The median is (2 + 3) / 2 = 2.5.
Example 03
Input
nums1 = [0,0], nums2 = [0,0]
Output
0.0
The merged sorted array is [0,0,0,0]. The median is 0.
03 · Constraints
- 01nums1.length == m
- 02nums2.length == n
- 030 <= m <= 1000
- 040 <= n <= 1000
- 051 <= m + n <= 2000
- 06-106 <= nums1[i], nums2[i] <= 106
04 · Optimal complexity
- Time
- O(log(min(m, n)))
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.