The Problem

Given two sorted arrays of size $m$ and size $n$, find the median of the merged array in $\mathcal{O}(log(min(m, n)))$ time.

Intuition

The naive solution would be to merge arrays and find median which takes linear time. We can do better than that. How?

The naive solution performs comparisons linearly on all elements it would take $\mathcal{O}(min(m, n))$. But we don’t really have to do all those comparisons, the only comparison we need to make are the ones which help us separate the merged array into two halves, middle of which is our median.

If your first array has $m$ elements, and the second one has $n$ elements, your merged array will have $m+n$ elements.

If I were to partition the first array into $x$ and $m-x$ elements, what does that leave me for performing a partition on the second array? Well, we need to part the second array in a way that both left and right halves together of both arrays have same number of elements (or the left has one less). So our second array has to be partitioned at $(m+n)/2 - x$ Think!. It should now be clear that the first array here dictates where to partition the second array to maintain the equality constraint.

However, median also needs the array to be sorted, so a partition which violates this constraint, isn’t acceptable to us. Hence the second constraint - All elements on left sides should be less than or equal to the ones on the right side.

Since our arrays are already sorted, all we need to check are the border elements.

Lets take an example of following arrays

If you have read solutions elsewhere, it might have puzzled you why would we flip the arrays? This is just to ensure that we always perform the binary search on the smaller array. If you don’t understand this part, it shall be more clear later. Hold on to that thought!

Since second one is shorter, lets flip.

Lets number the indices of the array. The first array now dictates where to partition.

Lets Partition - since size of first array is $m$, we partition at $m/2 = 5/2 = 2$. This implies that there are two elements on left side of the first array.

What does that leave for second array? $3$ on the left side, so that total on left side (in blue) = $5$ which is same or lesser than the number of elements on right side.

Before we jump onto comparing the border elements, lets name them for sake of clarity. Also, just notice for now how we move the window, it becomes more clear int the next step.

We need to make sure 2 things here:

  1. maxLeftX <= minRightY
  2. maxLeftY <= minRightX

If not, we need to check whether our partition on $X$ - (the first array aka nums1) needs to move left, or right. To do so, we just need to check how we’re doing on point (1) above. If maxLeftX > minRightY then we’re basically having too large elements in the first array, and we should shift our partition point to the left, otherise, to the right.

As shown in the above, we ask ourselves whether $16 <= 9$ and $7 <= 20$. False. Since $16$ (maxLeftY)is too big of a number than $9$, we need to move our partition to the right so that minRightX becomes larger or equal to that.

We perform a similar check on new partitions to know that we’ve finally satisfied all our constraints. Thus median is max(maxLeftX, maxLeftY) since the total $m+n$ is odd, and we have a single middle number (we do not need to average). Thus,

It is also helpful to see it visually, how it’d have looked - had we opted for the linear time approach:

Implementation

 public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        if(nums2.length < nums1.length){
            // To ensure that we always run search on the lesser devil
            return findMedianSortedArrays(nums2, nums1);
        }

        int x = nums1.length;
        int y = nums2.length;

        int low = 0;
        int high = x;

        while(low <= high){
            int partitionX = (low + high)/2;
            int partitionY = (x + y + 1)/2 - partitionX;
            
            // INF is added to cover edge cases when either of the 4 parts become empty.
            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX-1];
            int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY-1];
            int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if(maxLeftX <= minRightY && maxLeftY <= minRightX){
                if((x+y)%2 == 0){
                    return (double) (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY))/2;
                } else {
                    return (double) (Math.max(maxLeftX, maxLeftY));
                }

            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }

        }
        throw new IllegalArgumentException();

    }

This post is partly based on a video by Tushar Roy here. The aim was to provide a concise, visual representation of the same.

Feeling generous ? Help me write more blogs like this :)


Feeling even more generous ?

$20 can feed a poor child for a whole year. Akshaya Patra (Aak-sh-ayah pa-tra) is the world’s largest NGO school meal program, providing hot, nutritious school lunches to over 1.8 million children in 19,257 schools, across India every day. Your 20$ makes all the difference.