LeetCode 4: Median of Two Sorted Arrays

Problem summary

You are given two sorted arrays nums1 and nums2 of sizes m and n.
Find the median of the two sorted arrays. The overall run time complexity should be O(log(min(m, n))).
The median is the middle value for odd total length, or the average of two middle values for even total length.

Examples
Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5

Constraints and important notes

Arrays are already sorted.
Arrays can have different lengths; one may be empty.
Aim for O(log(min(m, n))) time.

Approach in simple English

A direct merge and then pick the middle elements is simple but costs O(m + n) time and O(1) extra space if merged virtually; however the problem asks for a faster O(log(min(m, n))) solution.

Key idea: perform a binary search on the smaller array to find a partition that splits both arrays into left and right halves such that:

number of elements in left halves = number of elements in right halves (or differ by 1 when total length is odd),
every element in left halves <= every element in right halves.

If such a partition is found, the median is:

if total length is odd: max(left halves)
if total length is even: average of max(left halves) and min(right halves)

How the binary search works, step-by-step:

Ensure we binary-search the smaller array (swap if needed).
Let i be partition index in the first array (number of elements taken from nums1 to the left side), and j be partition index in the second array computed so total left size = total right size (or left one larger).
- j = (m + n + 1) / 2 – i
Identify left and right boundary elements around partitions:
- Aleft = (i == 0) ? -infinity : nums1[i-1]
- Aright = (i == m) ? +infinity : nums1[i]
- Bleft = (j == 0) ? -infinity : nums2[j-1]
- Bright = (j == n) ? +infinity : nums2[j]
If Aleft <= Bright and Bleft <= Aright, partition is correct.
- If total length is odd, median = max(Aleft, Bleft).
- Else median = (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
If Aleft > Bright, move i left (reduce i). If Bleft > Aright, move i right (increase i).
Continue binary search until found.

Why this works: the correct partition guarantees left half contains the largest floor((m+n)/2) elements among the combined arrays and right half contains the remaining smallest elements. Binary searching the smaller array gives O(log(min(m, n))) time.

Java code (O(log(min(m,n))) solution)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Always binary search the smaller array
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0;
        int right = m;

        while (left <= right) {
            int i = (left + right) / 2; // partition in nums1
            int j = (m + n + 1) / 2 - i; // partition in nums2 to balance left/right

            int Aleft = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int Aright = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int Bleft = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int Bright = (j == n) ? Integer.MAX_VALUE : nums2[j];

            // Check if correct partition
            if (Aleft <= Bright && Bleft <= Aright) {
                // Found correct partition
                if ((m + n) % 2 == 1) {
                    return (double) Math.max(Aleft, Bleft);
                } else {
                    int leftMax = Math.max(Aleft, Bleft);
                    int rightMin = Math.min(Aright, Bright);
                    return (leftMax + rightMin) / 2.0;
                }
            } else if (Aleft > Bright) {
                // Too many elements taken from nums1, move left
                right = i - 1;
            } else {
                // Bleft > Aright, too few elements taken from nums1, move right
                left = i + 1;
            }
        }

        // Should never reach here if inputs are valid
        throw new IllegalArgumentException("Input arrays are not valid sorted arrays.");
    }
}

Explanation of sentinel values

Integer.MIN_VALUE and Integer.MAX_VALUE are used to represent negative and positive infinity for partition boundary comparisons. This simplifies handling boundaries when i or j is 0 or equal to length.

Dry run (detailed step-by-step)

Example 1 (odd total length)
nums1 = [1, 3], nums2 = [2]

m = 2, n = 1
We ensure nums1 is smaller; here nums2 is smaller, so swap in call: binary search on [2] and other as [1,3]. For clarity, treat arrays as:
A = [2] (m = 1)
B = [1, 3] (n = 2)

Initial:
left = 0, right = 1

Iteration 1:
i = (0 + 1)/2 = 0
j = (1 + 2 + 1)/2 – 0 = 2 (integer division: (4)/2 = 2)

Aleft = -inf (i == 0)
Aright = A[0] = 2
Bleft = B[j-1] = B[1] = 3
Bright = (j == n)? +inf? j==2 and n==2 so Bright = +inf

Check:
Aleft <= Bright -> -inf <= +inf true
Bleft <= Aright -> 3 <= 2 false

Since Bleft > Aright, need to move i right: left = i + 1 = 1

Iteration 2:
i = (1 + 1)/2 = 1
j = (4)/2 – 1 = 1

Aleft = A[0] = 2
Aright = +inf (i == m)
Bleft = B[0] = 1
Bright = B[1] = 3

Check:
Aleft <= Bright -> 2 <= 3 true
Bleft <= Aright -> 1 <= +inf true

Partition correct. Total length (m+n) = 3 is odd, median = max(Aleft, Bleft) = max(2, 1) = 2.0

Result: 2.0

Example 2 (even total length)
nums1 = [1, 2], nums2 = [3, 4]

m = 2, n = 2. Binary search on either (nums1 is already <= nums2 length).

Initial:
left = 0, right = 2

Iteration 1:
i = 1
j = (2 + 2 + 1)/2 – 1 = (5/2) – 1 = 2 – 1 = 1 (note integer division)
Aleft = nums1[0] = 1
Aright = nums1[1] = 2
Bleft = nums2[0] = 3
Bright = nums2[1] = 4

Check:
Aleft <= Bright -> 1 <= 4 true
Bleft <= Aright -> 3 <= 2 false

Since Bleft > Aright, move i right: left = i + 1 = 2

Iteration 2:
i = 2
j = (5/2) – 2 = 2 – 2 = 0
Aleft = nums1[1] = 2
Aright = +inf (i == m)
Bleft = -inf (j == 0)
Bright = nums2[0] = 3

Check:
Aleft <= Bright -> 2 <= 3 true
Bleft <= Aright -> -inf <= +inf true

Partition correct. Total length is 4 (even):
leftMax = max(Aleft, Bleft) = max(2, -inf) = 2
rightMin = min(Aright, Bright) = min(+inf, 3) = 3
median = (2 + 3) / 2.0 = 2.5

Result: 2.5

Complexity

Time: O(log(min(m, n))) — binary search on the smaller array.
Space: O(1) extra space.

Edge cases to watch

One array is empty. The median is the median of the non-empty array (handled by partitions and sentinel values).
Very different array lengths (small and huge). Always search the smaller array for efficiency.
Duplicates — algorithm handles duplicates fine.
Integer overflow is not an issue in comparisons; sentinel values are chosen safely. For the median average (leftMax + rightMin) / 2.0 the sum fits in an int if arrays contain int values; if concerned about extreme values, cast to long before summing: ( (long) leftMax + rightMin ) / 2.0.