Verbose solution, clear logical breakdown


  • 0
    E

    This problem really had me stumped and the most popular solutions did not help me fill in a few gaps in my reasoning. Here is a clear breakdown of my approach to the problem, hopefully this will help some people who had the same block as me. My code is intentionally more verbose than some of the solutions here for clarity of logic.

    Initial Approach

    Finding the median of a sorted array is easy. They have given us 2 sorted arrays so the obvious initial approach is to do an O(n) merge of the two arrays and quickly grab the median of the new, single, sorted array. O(n) isn't too bad, unfortunately we are specifically told we must do better.

    They have kindly told us that we are looking for a runtime complexity around: O(log (m+n)). Log(n) tells us we are very likely doing some sort of repeated division, ie. probably a binary search. Thanks for the hint!

    Medians and Why Do We Care

    What is so special about medians that we can use their unique qualities to improve our runtime by so much? 2 things in particular:

    • There are an equal number of elements on either side of the median
    • In an sorted list, all of the values to the left of the median are smaller or equal to all of the values on the right

    Now, we have 2 sorted arrays A and B. If we were infinitely wise we could chop these arrays each into two pieces so that the left halves of A and B (Aleft, Bleft) have exactly the same number of elements of the right halves of A and B (Aright, Bright) AND that all of the values in the two left halves are equal or less than all of the values in the right halves of A and B. Finding these 2 cut points (1 for each array) will give us the two conditions above and hence the median.

    Connecting the Cut Points

    We have now reduced the problem to finding two appropriate cut points i and j (i = cut point in A, j = cut point in B). This is great, but we need to do better than checking out every combination of i and j. How can we connect i and j?

    The first property of a median lets us do this. Because there must be an equal number of elements on either side of the median, if we cut the arrays each in two parts, we know num_elements(Aleft) + num_elements(Bleft) == num_elements(Aright) + num_elements(Bright). Using i and j: i + j == (A.length - i) + (B.length - j).

    In other words, there are multiple cut points that satisfy this condition, which only considers the number of elements, not their values BUT these cut points are bound together. If we move the cut point in A up one, we must decrease the cutpoint in B to keep the number of elements in each half the same. Rearranging the equation above, we get: j = (A.length + B.length) / 2 - i or : j = combined_length / 2 - i

    Binary Search for Cutpoint

    Now, we know need to find two cut points that satisfy the median conditions. We have just connected the two cut points together with an equation so actually we only need to find 1, namely i.

    i exists only in Array A so all we need to do now is search A for i such that the second median condition is true. A great array search that will give us O(log(n)) is a binary search.

    The check for if we have found the right cut points is easy. We check for max value of Aleft and Bleft and make sure it is less than or equal to the min value of Aright and Bright. Because the arrays are sorted for us, we only have to look at 4 elements to do this check and the indices are our cut points.

    Note, in the implementation, I use Integer.MIN_VALUE and Integer.MAX_VALUE to indicate the value when an index is off the end of an array. These numbers are only used in the check for the median condition, ie. if max value in Aleft is Integer.MIN_VALUE, we are off the left edge -> all of A is in Aright.

    Lastly, an easy optimization I found in stellari's solution is to make sure we are searching for i in the shortest of the 2 arrays. Might as well search the shortest one!

    Java Implementation

        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
            /* Median: The mid-point of a list of numbers (equal number of elements on either side) 
             * such that numbers to the left are all <= midpoint and numbers to the right are all >= midpoint
             *
             * So, there exists an i for nums1 and a j for nums2 such that:
             *   1 : num_elements(nums1[0]->nums1[i]) + num_elements(nums2[0]->nums2[j])
             *      == num_elements(nums1[i+1]->nums1[max]) + num_elements(nums2[j+1]->nums2[max])
             *   
             *   2 : max(nums1[i], nums2[j]) <= min(nums1[i+1], nums2[j+1]) 
             *
             * The 1st condition tells us the relationship between i and j.  Namely: j = (total_length / 2) - i
             * The 2nd condition is easy to check if we have an i (and hence a j from above equation)
             * We binary search for the i we need.
             *
             * Note: we are looking for a split point, this is "between" elements.  Ie. a split point of 0 means
             *      no numbers to the left of the split.
             *      So: i == 0 excludes the first element. i == 1 includes only it.
             *
             */
             
            int l1, l2, r1, r2;  //l1 is largest value in left side of nums1 after split, r1 smallest value on right, etc.
            double median = 0;
            int combined_length = nums1.length + nums2.length;
    
            //Low and high values for binary search in nums1 to find i
            int low = 0;
            int high = nums1.length;
            
            //We look for i in the shortest array for a faster search 
            if (nums1.length > nums2.length)
                return findMedianSortedArrays(nums2, nums1);
            
            //Boundary cases
            if (0 == combined_length)
                return 0.0;
                
            if (0 == nums1.length)
                return calculateMedian(nums2);
            
            if (0 == nums2.length)
                return calculateMedian(nums1);
             
             
            while (low <= high) {
                 
                int i = ((high - low) / 2) + low; 
                int j = (combined_length / 2) - i;
    
                //L and R sides for Array 1
                if (i <= 0) { 
                    l1 = Integer.MIN_VALUE;
                    r1 = nums1[0];
    
                } else if (i >= nums1.length) {
                    l1 = nums1[nums1.length -1];
                    r1 = Integer.MAX_VALUE;
    
                } else {
                    l1 = nums1[i-1];
                    r1 = nums1[i];
                }
    
                //L and R sides for Array 2
                if (j <= 0) { 
                    l2 = Integer.MIN_VALUE;
                    r2 = nums2[0];
    
                } else if (j >= nums2.length) {
                    l2 = nums2[nums2.length -1];
                    r2 = Integer.MAX_VALUE;
    
                } else {
                    l2 = nums2[j-1];
                    r2 = nums2[j];
                }
    
                //Did we find it?
                if (Math.max(l1, l2) <= Math.min(r1, r2)) {
                    median = calculateMedian(nums1, nums2, l1, l2, r1, r2); //Hooray!
                    break;
                }
                
                //i is too big, let's split lower
                if (r2 < l1)
                    high = i - 1;
                
                //i is too small, let's split higher
                else
                    low = i + 1;
             }
             
             return median;
        }
        
        private static double calculateMedian (int[] nums) {
            boolean is_even = (nums.length % 2) == 0;
            double median = 0;
            int midpoint = nums.length / 2;
            
            if (0 == nums.length)
                return 0;
            
            if (is_even) 
                median = (nums[midpoint-1] + nums[midpoint]) / 2.0;    
            else
                median = nums[midpoint];
            
            return median;
        }
    
        private static double calculateMedian (int[] nums1, int[] nums2, int l1, int l2, int r1, int r2) {
            boolean is_even = ((nums1.length + nums2.length) % 2) == 0;
            double median = 0;
            
            if (is_even) 
                median = (Math.max(l1,l2) + Math.min(r1,r2)) / 2.0;    
            else
                median = Math.min(r1, r2);
            
            return median;
        }
    }```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.