Crack the Backend

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays. The overall run time should be O(log (m+n)). If the merged array has an odd length, the median is the middle element; if even, it is the average of the two middle elements.

We cannot merge the arrays (that would be O(m+n)). We use a partition idea: imagine a partition that splits the merged sorted array into a left half and a right half of equal (or nearly equal) size. The median is determined by the elements around that partition.

Key Observations

Partition approach: We want the left half of the merged array to have (m+n+1)/2 elements. Partition nums1 at index i (left part nums1[0..i-1], right nums1[i..m-1]) and nums2 at index j so that i + j = (m+n+1)/2. The left half has max(nums1[i-1], nums2[j-1]) as its max; the right half has min(nums1[i], nums2[j]) as its min. For a valid partition we need maxLeft1 <= minRight2 and maxLeft2 <= minRight1. Binary search on i (in the smaller array) and compute j; adjust lo/hi based on the comparison. Median = (maxLeft + minRight) / 2 or just maxLeft if total length is odd.

Approach

High-level: Ensure nums1 is the shorter array. Binary search on i (cut in nums1). j = (m+n+1)/2 - i. Check maxLeft1 <= minRight2 and maxLeft2 <= minRight1. If maxLeft1 > minRight2, i is too large (hi = i - 1); if maxLeft2 > minRight1, i is too small (lo = i + 1). When valid, median = (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2 (or just max(maxLeft1, maxLeft2) if total length odd).

Steps:

If nums1.length > nums2.length, swap so we binary search on the smaller array. m = nums1.length, n = nums2.length, half = (m+n+1)/2.
lo = 0, hi = m. While lo <= hi: i = (lo+hi)/2, j = half - i. Get maxLeft1, minRight1, maxLeft2, minRight2 (use -inf/+inf at boundaries). If maxLeft1 <= minRight2 && maxLeft2 <= minRight1, compute and return median. Else if maxLeft1 > minRight2, hi = i - 1; else lo = i + 1.
Return median value.

Implementation

Java

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

    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.length, n = nums2.length;
    int lo = 0, hi = m;

    while (lo <= hi) {
        int i = (lo + hi) / 2, j = (m + n + 1) / 2 - i;
        int maxL1 = i == 0 ? Integer.MIN_VALUE : nums1[i-1];
        int minR1 = i == m ? Integer.MAX_VALUE : nums1[i];
        int maxL2 = j == 0 ? Integer.MIN_VALUE : nums2[j-1];
        int minR2 = j == n ? Integer.MAX_VALUE : nums2[j];

        if (maxL1 <= minR2 && maxL2 <= minR1) {
            if ((m+n) % 2 == 0) {
                return (Math.max(maxL1, maxL2) + Math.min(minR1, minR2)) / 2.0;
            }

            return Math.max(maxL1, maxL2);
        }

        if (maxL1 > minR2) {
            hi = i - 1;
        }
        else {
            lo = i + 1;
        }
    }

    return 0;
}

Test Cases

Example 1

Input

nums1 = [1,3], nums2 = [2]

Expected

2.0

Explanation

Merged [1,2,3], median 2.

Complexity Analysis

Time: O(log(min(m,n))).
Space: O(1).

Follow-ups

K-th element of two sorted arrays (generalize).