Median of 2 sorted arrays
PayPal
PaytmThe problem
Given two sorted arrays arr1 and arr2 of size m and n respectively, return the median of the two sorted arrays.
The median is defined as the middle value of a sorted list of numbers. In case the length of the list is even, the median is the average of the two middle elements.
Input: arr1 = [2, 4, 6], arr2 = [1, 3, 5] Output: 3.5 Explanation: The array after merging arr1 and arr2 will be [ 1, 2, 3, 4, 5, 6 ]. As the length of the merged list is even, the median is the average of the two middle elements. Here two medians are 3 and 4. So the median will be the average of 3 and 4, which is 3.5.
Input: arr1 = [2, 4, 6], arr2 = [1, 3] Output: 3.0 Explanation: The array after merging arr1 and arr2 will be [ 1, 2, 3, 4, 6 ]. The median is simply 3.
Input: arr1 = [2, 4, 5], arr2 = [1, 6]
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= arr1[i], arr2[i] <= 106
cpp
class Solution {
public:
double median(vector<int> &arr1, vector<int> &arr2) {
}
};java
class Solution {
public double median(int[] arr1, int[] arr2) {
}
}python
class Solution:
def median(self, arr1, arr2):javascript
class Solution {
median(arr1, arr2) {
}
}csharp
class Solution
{
public double Median(List<int> arr1, List<int> arr2)
{
}
}go
func median(arr1 []int, arr2 []int) float64 {
}Stuck? Show a way to structure it+
- 01Binary-search a partition in the smaller array.
- 02Make the combined left partition half the total size.
- 03Validate cross-boundary ordering.
- 04Use max-left for odd totals.
- 05Average max-left and min-right for even totals.
Reference answer
Then expect these follow-ups
Why search only the shorter array?
Tests: bounds
How does kth-element differ?
Tests: comparison
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question