Edward on Java with Leetcode: 4. Median of Two Sorted Arrays

Photo by McGill Library on Unsplash

Problem

Problem description is available at 4. Median of Two Sorted Arrays.

Algorithm

This video (audio in Chinese) explains very clear how to solve the problem. I’m just going to explain in English with my own words.

First go to the foundamental thing: what needs to be done exactly? To find the middle value(s) of the merged array (imaging I merge them). Assume the lengths of array 1 and 2 is L1 and L2, therefore total length is L=L1+L2, if the total number is even, I should find L/2th and (L/2+1)th numbers; if the total number is odd, I should find (L/2+1)th.

Now let me use K to represent L/2 (in case of even) or (L/2+1). If I can pick totally smallest K numbers from the merged array, and n1 from nums1 while n2 from nums2, then the median is

max(nums1[n1–1], nums2[n2–1]) in case L is odd

or

(max(nums1[n1–1], nums2[n2–1]) + min(nums1[n1], nums2[n2])) in case L is even

Certainly n1 can be either 0 (indicating no numbers from nums1 is seleted into the set of K due to either it’s empty or every number in nums1 is larger than the maximum of nums2) or L1 (meaning all numbers from nums1 is seleted into the set of K). Same thing can happen to n2. In those corner cases, n1–1, n2–1 and etc. need to be carefully inspected to make sure when they are used as an array index, array boundary will not be crossed.

cut1, cut2 indicates the cutting line (not inclued themselves)

Binary search is used to determine the postion of cut1and cut2can be concluded from using K-cut1 so that required time complexity (Olog(L1+L2)) can be met.

Java Solution

In above #2, I mention the “fast forward the left side” which means if the right side now is charactor X, I want to see what’s the position of X in the existing window [left, right). The easiest way to achieve that is if I have a hashmap whose keys are charactors and values are positions.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int L1 = nums1.length;
        int L2 = nums2.length;
        
        if (L1 > L2) return findMedianSortedArrays(nums2, nums1);

        int L = L1 + L2;
        /*
            Thanks to https://www.youtube.com/watch?v=ScCg9v921ns 
            (audio in Chinese).
            if L is even, I need to find the (L/2)th and (L/2+1)th;
            if L is odd, I need to find the (L/2+1)th
            use K to represent L/2 (in case of even) or (L/2+1)
            if I can pick totally smallest K numbers from both nums1 and nums2,
            then the biggest one is the answer or the first part of the answer
        */
        int K = ( L % 2 == 1) ? L/2+1 : L/2;
        int start1 = 0, end1 = L1;
        while(start1 <= end1){
            int cut1   = (start1 + end1) / 2;
            int left1  = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];
            int right1 = (cut1 < L1) ? nums1[cut1] :Integer.MAX_VALUE; 
            int cut2   = K - cut1;
            int left2  = (cut2 <= 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
            int right2 = (cut2 < L2) ? nums2[cut2] :Integer.MAX_VALUE; 

            if (left1 <= right2 && left2 <= right1){
                int val1 = Math.max(left1, left2);
                return ( L % 2 == 1) ? val1 : 
                  ((double)(Math.min(right1, right2) + val1)) /2;
            }
            else{
                if (left1 > right2) end1 = cut1 - 1;
                if (left2 > right1) start1 = cut1 + 1;
            }
        }

        //If we run here, either L1 = 0 or nums1[0] > nums2[the last one]
        return ( L % 2 == 1) ? nums2[L/2] : 
          ((double)(nums2[L/2-1] + nums2[L/2])/2);
    }
}

Java Knowledge

1. It’s pretty confusing but Java.String has a method called length()while an array’s size can be retrieved by using lengthproperty.
2. Java has an embeded package called Math. In above, I use Math.minto get the minimum of two.