Friday, 21 May 2021

Java Program to Solve Median of Two Sorted Array Problem

Median of two sorted arrays is a common problem which is asked in companies like Amazon, Google, Microsoft & Goldman Sachs. You can find the question in InterviewBit or LeetCode.

Problem: 
We have two sorted arrays A and B of size m and n respectively. We need to find the median of these two sorted arrays ( median of the array formed by merging both arrays ). The run time complexity should be O(log (m+n)).

Input:
A : [1 4 6]
B : [2 5]
Output: 4

Input:
A : [1 3 5]
B : [2 4 6]
Output: 3.5 ( (3 + 4) / 2.0 = 3.5 )

We can actually merge the two arrays & find out the median. But it will take O(m+n) time complexity.

We know the size of the median partition. In above cases it is 3. Median of 5 elements is 3 & median of 6 elements is avg of 3rd & 4th elements.
But left side elements in the partition can be part of both the arrays.
So we need to find indexes in both arrays where combined left side elements count is same as median partition. And elements in left hand side of each partition is less than the right side partitions of both arrays.

We can use binary search on the smaller size array to find the partition index. So time complexity will be O(log(min(m, n))).

You can find the working Java program for this problem below.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    // DO NOT MODIFY BOTH THE LISTS
    public double findMedianSortedArrays(final List<Integer> a, final List<Integer> b) {
        if(a.size() > b.size()){
            return findMedianSortedArrays(b, a);
        }
        int start = 0;
        int end = a.size() - 1;
        while(start <= end){
            int partition = (end + start) / 2 ;
            int bPartition = (a.size() + b.size() - 1) / 2 - partition - 1;
            int aRightValue = partition == a.size()-1 ? Integer.MAX_VALUE : a.get(partition + 1);
            int bRightValue = bPartition == b.size()-1 ? Integer.MAX_VALUE : b.get(bPartition + 1);
            int aLeftValue = partition < 0 ? Integer.MIN_VALUE : a.get(partition);
            int bLeftValue = bPartition < 0 ? Integer.MIN_VALUE : b.get(bPartition);
            if(aLeftValue <= bRightValue && bLeftValue <= aRightValue){
                if((a.size() + b.size()) % 2 == 1){
                    return Math.max(aLeftValue, bLeftValue);
                } else {
                    return (Math.max(aLeftValue, bLeftValue) + 
                           Math.min(aRightValue, bRightValue)) / 2.0;
                }
            } else if(aLeftValue > bRightValue){
                end = partition - 1;
            } else {
                start = partition + 1;
            }
        }
 
        int totalSize = a.size() +  b.size();
        // either A is empty or partition elements are less than starting element of A
        if(totalSize % 2 == 1) {
            return b.get(totalSize / 2);
        } else {
            int leftValue = b.get((totalSize - 1)/ 2);
            int rightValue = b.get(totalSize / 2);
            if(!a.isEmpty() && a.get(0) < rightValue) {
                rightValue = a.get(0);
            }
            return (leftValue +  rightValue) / 2.0;
        }
    }
}

No comments:

Post a Comment

Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...