Median of Two Sorted Arrays: the idea to remember.

The core insight

Choose complementary partitions with half the elements on the left, then compare the four boundary values.

Why it works

When both left boundaries are no greater than the opposite right boundaries, every left value precedes every right value.

The mistake to avoid

Search the smaller array, allow empty partitions, and widen before adding the two middle values.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Choose complementary partitions with half the elements on the left, then compare the four boundary values.
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;

    if (m > n) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int total = m + n;
    int half = (total + 1) / 2;

    int left = 0;
    int right = m;

    var result = 0.0;

    while (left <= right) {
        int i = left + (right - left) / 2;
        int j = half - i;


        int left1 = (i > 0) ? nums1[i - 1] : Integer.MIN_VALUE;
        int right1 = (i < m) ? nums1[i] : Integer.MAX_VALUE;
        int left2 = (j > 0) ? nums2[j - 1] : Integer.MIN_VALUE;
        int right2 = (j < n) ? nums2[j] : Integer.MAX_VALUE;


        if (left1 <= right2 && left2 <= right1) {

            if (total % 2 == 0) {
                result =
                    ((long)Math.max(left1, left2) + Math.min(right1, right2)) /
                    2.0;

            } else {
                result = Math.max(left1, left2);
            }
            break;
        }

        else if (left1 > right2) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }

    return result;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection