Coding

Median of 2 sorted arrays

Asked at

PayPal

Paytm

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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)
    {
      
    }
}

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

Partition the two arrays so the left side contains (m+n+1)/2 values. Binary-search the cut in the smaller array and derive the cut in the other. With sentinel values at array ends, a partition is correct when leftA <= rightB and leftB <= rightA. If the total count is odd, the median is max(leftA,leftB); if even, it is (max(leftA,leftB) + min(rightA,rightB))/2. Move the first cut left when leftA > rightB, otherwise right. Binary-searching the smaller array is O(log min(m, n)) time and O(1) auxiliary space. Use a wide type before averaging to avoid overflow, and ensure floating division for an even median.

Then expect these follow-ups

Why search only the shorter array?
Tests: bounds
How does kth-element differ?
Tests: comparison

Hiring now

PayPal has 254 open roles right now

Also hiring: Paytm

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Sr Manager, Partnership Marketing
Chicago, Illinois, United States of America
Lead Product Manager
San Jose, California, United States of America
Sr Software Engineer
Bangalore, Karnataka, India

Or practice this question first

Next question