LeetCode problem 4#: Median of Two Sorted Arrays solution

LeetCode problem #4, “Median of Two Sorted Arrays,” is a frequently encountered challenge in coding interviews. This problem requires finding the median of two sorted arrays. We’ll present solutions for this problem in both Java and Python, providing detailed explanations for each approach.

Problem Statement:

Given two sorted arrays, nums1 and nums2, of sizes m and n respectively, return the median of the two sorted arrays.

Java Solution:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        int[] temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }

    int m = nums1.length;
    int n = nums2.length;
    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;

    while (iMin <= iMax) {
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;

        if (i < m && nums2[j-1] > nums1[i]) {
            iMin = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            iMax = i - 1;
        } else {
            int maxLeft;
            if (i == 0) maxLeft = nums2[j-1];
            else if (j == 0) maxLeft = nums1[i-1];
            else maxLeft = Math.max(nums1[i-1], nums2[j-1]);

            if ((m + n) % 2 == 1) return maxLeft;

            int minRight;
            if (i == m) minRight = nums2[j];
            else if (j == n) minRight = nums1[i];
            else minRight = Math.min(nums1[i], nums2[j]);

            return (maxLeft + minRight) / 2.0;
        }
    }

    throw new IllegalArgumentException("Input arrays are not sorted.");
}

Python Solution:

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    i_min, i_max, half_len = 0, m, (m + n + 1) // 2

    while i_min <= i_max:
        i = (i_min + i_max) // 2
        j = half_len - i

        if i < m and nums2[j-1] > nums1[i]:
            i_min = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            i_max = i - 1
        else:
            max_left = 0
            if i == 0: max_left = nums2[j-1]
            elif j == 0: max_left = nums1[i-1]
            else: max_left = max(nums1[i-1], nums2[j-1])

            if (m + n) % 2 == 1: return max_left

            min_right = 0
            if i == m: min_right = nums2[j]
            elif j == n: min_right = nums1[i]
            else: min_right = min(nums1[i], nums2[j])

            return (max_left + min_right) / 2.0

Explanation:

This problem demands finding the median of two sorted arrays, which can be efficiently solved using binary search. The solutions presented here effectively handle various edge cases, ensuring optimal performance.

Both the Java and Python solutions operate with a time complexity of O(log(min(m, n))). This approach provides an efficient way to solve the problem with minimal computational overhead.

By understanding and implementing these solutions, you’ll be well-equipped to tackle similar challenges and excel in coding interviews. Keep practicing, and you’ll continue to enhance your problem-solving skills!