top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Search

Median of Array InterviewBit Solution


Problem Description:

There are two sorted arrays A and B of size m and n respectively.

Find the median of the two sorted arrays ( The median of the array formed by merging both the arrays ).

The overall run time complexity should be O(log (m+n)).


Sample Input

Input: 
    A : [1 4 5] 
    B : [2 3]

Sample Output

Output: 3

Note: IF the number of elements in the merged array is even, then the median is the average of (n / 2)th and (n/2 + 1)th element.

For example, if the array is [1 2 3 4], the median is (2 + 3) / 2.0 = 2.5



Approach:


Let us have two arrays A and B with size n1 and n2 respectively. So if we combine these two arrays we would get an array of size (n1 + n2).

To find median of this array we would have to go for ((n1 + n2) / 2)th element. 

So let, half = (n1 + n2)/2; 
And do binary search on any one array, in our case we have taken the array with the minimum size, we would call it A here.

So in our binary search, suppose m1 is the current index of our array A. Then if we are interested in ((n1 + n2) / 2)th i.e. half, then m2 (current index of array B) would be equal to half - m1.

As we need, m1 + m2 = half

Now, we have three conditions:

  1. if A[m1] < B[m2 - 1], that means the current index is too small, to be at mid.

  2. if B[m2] < A[m1 - 1], that means the current index is too large, to be at mid.

  3. Otherwise, we found our cut.

Reason: 

Condition 1: A[m1] < B[m2 - 1],
    - That means there might exist some indexes greater than m1, that are smaller than B[m2 - 1]. That's why we have to move the current index towards right. Because when we move m1 to the right, m2 would shift towards left.
Condition 2: B[m2] < A[m1 - 1],
    - That means there might exist some indexes greater than m2, that are smaller than A[m1 - 1]. That's why we have to move the current index towards left. Because when we move m1 to the left, m2 would shift towards right.
Condition 3: When we found our cut.
    - So now we have to check whether (n1 + n2) is odd or not, if it is odd, then return the max value from the left side.
    - If it is not odd, then we have to find min value from the right side as well. And then return (maxLeft + minRight)/2.


Time & Space Complexity:

Time Complexity: O(log(min(n,m)))

- where n & m are the size of two arrays.

Space Complexity: O(1)

- as we have not taken extra space (Ignoring space taken by the given arrays)


Solution:


Code in C++


Tags:

bottom of page