4. Median of Two Sorted Arrays

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)

View Leetcode Problem

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!");
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.