I was stuck on this problem for like 2 days until I finally decided to see the solution..... (rip). This is my solution + some notes to this problem.. thank u

Problem statement (Leetcode Hard)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] A = nums1;
        int[] B = nums2;
        int total = A.length + B.length;
        // int half = total / 2;
        int half = (total + 1) / 2; // we + 1 to make sure the median is always on the left partition

        // make A the shorter one
        if (B.length < A.length) {
            int[] tmp = A;
            A = B;
            B = tmp;
        }

        int l = 0;
        int r = A.length;
        // it's not A.length - 1 because i or j represents the start of the right (the "cut")
        // we need this to consider the case where ALL elements are in the left side (and 0 to the right)
        while (l <= r) {
            int i = (l + r) / 2; // start of ARight.. or more like a place to "cut"
            int j = half - i; // start of BRight

            int Aleft = i > 0 ? A[i - 1] : Integer.MIN_VALUE;
            int Aright = i < A.length ? A[i] : Integer.MAX_VALUE;
            int Bleft = j > 0 ? B[j - 1] : Integer.MIN_VALUE;
            int Bright = j < B.length ? B[j] : Integer.MAX_VALUE;

            if (Aleft <= Bright && Bleft <= Aright) {
                if (total % 2 != 0) { // total is odd, return the max of the lefts
                    return Math.max(Aleft, Bleft);
                } else { // total is even, we get the middle (max of lefts + min of rights) / 2
                    return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.0;
                }
            } else if (Aleft > Bright) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return -1;
    }
}

Concept

• Imagine we merged those 2 arrays. We want to get the Left partition and the Right partition, then get the median.
• But since we can’t merge, we need to find the partition (cut) that divides the combined set of numbers into 2 equal halves (left and right)

Strategy

(shoutout to neetcode)

• The main idea is that we have a Left and Right partition, and we check Aleft <= Bright && Bleft <= Aright
• If so, that means we have successfully found the left and right partition
  • If total is an odd number, then get Main.min(Aright, Bright)
  • If total is an even number, get (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2
• If not, if Aleft > Bright
  • That means when we combine all our lefts, in the left partition we have an element that is bigger than one element on the right partition
  • we have to shrink Aleft and expanding Bleft, so r = i - 1
• else (Bleft > Aright)
  • That means when we combine all our lefts, in the left partition we have an element that is bigger than one element on the right partition
  • we have to shrink Bleft and expanding Aleft -> l = i + 1

Things to note

• int total = A.length + B.length;, and int half = (total + 1) / 2
  • we + 1 to make sure the median is always on the left partition
  • If total is 10, then 10 + 15/ 2 = 6 (L and R has same # of elems). If total is 11, then 11 + 1 / 2 = 6 (L has 6, R has 5).
    • Both cases, L is either same or larger than R, so median will always be in L
• int l = 0 and int r = A.length
  • We do r = A.length and not A.length - 1 because we want to allow the possibility that ALL elements of A are smaller than the median (they are all Left partition and NO right partition)
  • If Bleft > Aright: l = i + 1 (the else case)
    • (Tracing example with A = [1,2], B = [3,4,5,6])
    • l can reach up to r, then i = (1+r)/2 can be exactly A.length, which means all of A is in the left partition
• The Integer.MIN_VALUE and Integer.MAX_VALUE
  • We give the MIN_VALUE to the lefts and the MAX_VALUE to the rights because if they are out of bounds, when we compare the check we want it to pass

Time Complexity

• We actively look for the "cut" position i (the start of Aright, which ranges from 0 to A.length) using binary search.

• The problem states that the solution must run $O(\log(m+n))$ time.

  • This would be the case if we had done a brute force solution - merging arrays together and then finding the median.

• But in the problem, we're actually just doing binary search on the shorter array (which is A in our case), so the actual time complexity is $(\log(\min(m,n)))$.