Is Median of Two Sorted Arrays easy or hard?

Median of Two Sorted Arrays is categorized as a hard problem because the optimal solution requires a non‑obvious binary search partition technique. Many candidates initially attempt a merge-based solution, but the interview expectation is the logarithmic binary search approach.

Median of Two Sorted Arrays Python/Java solution

Implementations typically follow the binary search partition method. The algorithm repeatedly adjusts the partition of the smaller array while computing the corresponding partition in the second array. Python, Java, C++, and JavaScript implementations all follow the same logic with constant extra space and O(log(min(m,n))) time.

What is the best approach for Median of Two Sorted Arrays?

The best approach uses binary search on the smaller array to find a valid partition between the two arrays. This method ensures the left half and right half of the combined arrays are correctly balanced. It runs in O(log(min(m,n))) time with O(1) extra space, making it the optimal solution for large inputs and interview settings.

Is Median of Two Sorted Arrays asked at Google/Amazon/Meta?

Median of Two Sorted Arrays is a well-known hard interview problem frequently associated with companies like Google, Amazon, and Meta. It tests binary search reasoning, handling edge cases, and understanding partition-based algorithms on sorted arrays.

What data structure is used in Median of Two Sorted Arrays?

The problem primarily uses arrays and binary search. The optimal solution manipulates partition indices within two sorted arrays and compares boundary elements to maintain ordering across the combined halves.

What is the time complexity of Median of Two Sorted Arrays?

The optimal algorithm runs in O(log(min(m,n))) time using a binary search partition strategy. A simpler approach merges both arrays and finds the middle element, which takes O(m + n) time. The binary search method is preferred because it reduces the search space dramatically.

How to solve Median of Two Sorted Arrays in O(log(min(m,n)))?

Perform binary search on the smaller array to choose a partition index. Compute the corresponding partition in the second array so the left halves contain half of the total elements. Adjust the search until the largest element on the left side is less than or equal to the smallest element on the right side. Once valid, compute the median from the boundary values around the partitions.

Description Solution Video 22:22

4. Median of Two Sorted Arrays

Hard47.9% acceptance45 companies

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⁶ <= nums1[i], nums2[i] <= 10⁶

Asked at top 20 of 45 companies

Yahoo Rippling Dropbox Zenefits VMware Adobe Autodesk Udemy GE Healthcare

Google Amazon Microsoft

+8 more

Meta Bloomberg Goldman Sachs Walmart Labs Wix Cognizant Capgemini Zeta

Topics

22:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

4. Median of Two Sorted Arrays

Asked at top 20 of 45 companies

Topics

Similar problems