The problem asks you to find the median of two sorted arrays. Use binary search to optimize the process, reducing time complexity to O(log(min(m, n))). By searching through the valid answer space, you efficiently determine the median of merged arrays without needing to merge them fully.
Problem Statement
Given two sorted arrays, nums1 and nums2, of sizes m and n respectively, find the median of the two sorted arrays. The merged array of both should be in non-decreasing order. The overall runtime complexity should be O(log(m+n)).
For example, when nums1 = [1,3] and nums2 = [2], the correct output is 2.0 as the median. The goal is to find a solution that avoids merging the arrays entirely, but instead utilizes a binary search approach over the valid answer space.
Examples
Example 1
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
merged array = [1,2,3] and median is 2.
Example 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
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
- -106 <= nums1[i], nums2[i] <= 106
Solution Approach
Binary Search Over the Smaller Array
To find the median without merging the arrays, perform binary search on the smaller of the two arrays, nums1 and nums2. This limits the search space, ensuring that you efficiently narrow down the correct partition to find the median.
Partition the Arrays
Divide both arrays into two parts where the left part contains smaller elements and the right part contains larger ones. The goal is to balance these partitions such that the left partition contains the same number of elements (or one more) than the right partition.
Handle Even and Odd Lengths
If the total length of the merged arrays is odd, the median is the maximum of the left partition. If even, it's the average of the maximum of the left partition and the minimum of the right partition.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(\log(\min(m, n))) |
| Space | O(1) |
The time complexity of this solution is O(log(min(m, n))) because we perform binary search on the smaller of the two arrays. The space complexity is O(1) since we only use a few variables to track the partition points.
What Interviewers Usually Probe
- The candidate demonstrates a clear understanding of binary search over a valid answer space.
- The candidate can explain how the partitioning logic helps in avoiding unnecessary merging of arrays.
- The candidate can handle edge cases, like odd or even total lengths, while maintaining time efficiency.
Common Pitfalls or Variants
Common pitfalls
- Confusing partitioning logic can lead to incorrect median calculations.
- Failing to account for edge cases where one array is empty or the partitioning is imbalanced.
- Over-complicating the solution by attempting to merge the arrays instead of using binary search.
Follow-up variants
- Handling arrays with significantly different lengths (m << n or n << m).
- Solving the problem with multiple edge cases like empty arrays.
- Optimizing for very large input arrays (up to 2000 elements).
How GhostInterview Helps
- GhostInterview guides you through the binary search approach, ensuring you understand how to search the valid answer space.
- GhostInterview helps you break down partitioning the arrays and managing edge cases efficiently.
- GhostInterview offers insights into optimizing for large inputs and understanding runtime complexities.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How do I approach the 'Median of Two Sorted Arrays' problem?
Use binary search over the smaller array to partition the arrays such that the left side has equal or one more element than the right side. Then, find the median by comparing the partition elements.
What is the time complexity of this solution?
The time complexity is O(log(min(m, n))) because binary search is performed on the smaller array.
What happens if one of the arrays is empty?
If one of the arrays is empty, the solution reduces to finding the median of the non-empty array.
How do I find the median when the total length is even?
When the total length is even, the median is the average of the maximum element in the left partition and the minimum element in the right partition.
What if the input arrays are very large?
The algorithm still works efficiently for large arrays, with O(log(min(m, n))) time complexity, which ensures that even large inputs can be handled quickly.
Need direct help with Median of Two Sorted Arrays instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Median of Two Sorted Arrays from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Efficiently search for a target in a 2D matrix using binary search and matrix properties.
Open problem page#315 Count of Smaller Numbers After SelfSolve the Count of Smaller Numbers After Self problem using binary search and optimized algorithms.
Open problem page#327 Count of Range SumCount the number of subarray sums within a given inclusive range using optimized divide-and-conquer techniques efficiently.
Open problem page