LeetCode 4: Median of Two Sorted Arrays Solution

Master LeetCode problem 4 (Median of Two Sorted Arrays), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

4. Median of Two Sorted Arrays

Hard

Array Binary Search Divide and Conquer

Problem Explanation

Explanation

To find the median of two sorted arrays efficiently, we can use the concept of binary search. By partitioning both arrays into two parts at different positions, we can ensure that elements on the left side are smaller than elements on the right side. The median will then be the average of the maximum element on the left side and the minimum element on the right side. We adjust the partition positions based on the comparison of elements to maintain this property.

Initialize variables m, n, low, high, leftMax, rightMin, and perform binary search on the smaller array.
Calculate partition positions partitionX and partitionY using binary search.
Update the partition positions based on the comparison of elements to ensure the property mentioned above.
Calculate the median based on the number of elements in the combined arrays.

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

Solution Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.length;
        int n = nums2.length;
        int low = 0, high = m;
        
        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (m + n + 1) / 2 - partitionX;
            
            int leftMaxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int rightMinX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
            
            int leftMaxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int rightMinY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];
            
            if (leftMaxX <= rightMinY && leftMaxY <= rightMinX) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(leftMaxX, leftMaxY) + Math.min(rightMinX, rightMinY)) / 2.0;
                } else {
                    return Math.max(leftMaxX, leftMaxY);
                }
            } else if (leftMaxX > rightMinY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        
        throw new IllegalArgumentException("Input arrays are not sorted!");
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 4 (Median of Two Sorted Arrays)?

This page provides optimized solutions for LeetCode problem 4 (Median of Two Sorted Arrays) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 4 (Median of Two Sorted Arrays)?

The time complexity for LeetCode 4 (Median of Two Sorted Arrays) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 4 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 4 in Java, C++, or Python.

Back to LeetCode Solutions