Problem Explanation

Given two sorted arrays nums1 and nums2, we are asked to find the median of these two arrays. The median of a sorted list of numbers is the middle value when the numbers are sorted in order. If the list has an even number of observations, the median is essentially the average of the two middle numbers.

For example, if nums1 = [1, 3] and nums2 = [2], the median is 2.0; if nums1 = [1, 2] and nums2 = [3, 4], the median is (2 + 3)/2 = 2.5

Approach

The idea behind the algorithm used in the solution is binary search. Because both arrays are sorted, to find the median, we essentially wish to find a point in the lists where the elements on the left side are less than the median and the elements on the right side are greater than the median. We can consider the smaller size list and perform a binary search to find a point which divides the list such that this is the case. After finding our partitions, we calculate maxLeft (maximum of left partition) and minRight (minimum of right partition). If maxLeft is less than or equal to minRight, it denotes that we have split the arrays correctly, else we adjust our binary search start and end.

Walkthrough

Suppose nums1 = [1,3] and nums2 = [2].

Size of nums1 = 2, size of nums2 = 1.

We perform binary search in the smaller list i.e., nums2.

Our aim is to partition the two lists such that at the cut off maxLeft <= minRight.

Performing these operations gradually we will get the median of the given merged list.

Let's see the solutions now:

JAVA Solution

1
2java
3class Solution {
4    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
5        // Check and process for the smallest array,
6        if (nums1.length > nums2.length) {
7            int[] temp = nums1; 
8            nums1 = nums2; 
9            nums2 = temp;
10        }
11        int x = nums1.length;
12        int y = nums2.length;
13        int left = 0;
14        int right = x;
15
16        // Using binary search
17        while (left <= right) {
18            int partitionX = (left + right) / 2;
19            int partitionY = (x + y + 1) / 2 - partitionX;
20            
21            int maxLeftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX - 1];
22            int minRightX = partitionX == x ? Integer.MAX_VALUE : nums1[partitionX];
23            
24            int maxLeftY = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY - 1];
25            int minRightY = partitionY == y ? Integer.MAX_VALUE : nums2[partitionY];
26            
27            if(maxLeftX <= minRightY && maxLeftY <= minRightX){
28                if ((x + y) % 2 == 0) {
29                    return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
30                } else {
31                    return Math.max(maxLeftX, maxLeftY);
32                }
33            } else if (maxLeftX > minRightY) {
34                right = partitionX - 1;
35            } else {
36                left = partitionX + 1;
37            }
38        }
39        throw new IllegalArgumentException("Input arrays are not right");
40    }
41}

Python Solution

1
2python
3class Solution:
4    def findMedianSortedArrays(self, nums1, nums2):
5        # ensure nums1 is smaller than nums2
6        if len(nums1) > len(nums2):
7            nums1, nums2 = nums2, nums1
8        
9        x, y = len(nums1), len(nums2)
10        lo = 0
11        hi = x
12        
13        while lo <= hi:
14            partition1 = (lo + hi) // 2
15            partition2 = (x + y + 1) // 2 - partition1
16            
17            maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
18            minRight1 = float('inf') if partition1 == x else nums1[partition1]
19            
20            maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
21            minRight2 = float('inf') if partition2 == y else nums2[partition2]
22            
23            if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
24                if (x + y) % 2 == 0:
25                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
26                else:
27                    return max(maxLeft1, maxLeft2)
28            elif maxLeft1 > minRight2:
29                hi = partition1 - 1
30            else:
31                lo = partition1 + 1
32                
33        raise Exception("Arrays are not sorted properly")

C++ Solution

1
2cpp
3double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
4    int n1 = nums1.size();
5    int n2 = nums2.size();
6    if (n1 > n2) {
7        return findMedianSortedArrays(nums2, nums1);
8    }
9
10    int k = (n1 + n2 + 1) / 2;
11    int l = 0;
12    int r = n1;
13
14    while (l < r) {
15        int m1 = l + (r - l) / 2;
16        int m2 = k - m1;
17        if (nums1[m1] < nums2[m2 - 1]) {
18            l = m1 + 1;
19        } else {
20            r = m1;
21        }
22    }
23
24    int m1 = l;
25    int m2 = k - l;
26
27    int c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1],
28                 m2 <= 0 ? INT_MIN : nums2[m2 - 1]);
29
30    if ((n1 + n2) % 2 == 1) {
31        return c1;
32    }
33
34    int c2 = min(m1 >= n1 ? INT_MAX : nums1[m1],
35                 m2 >= n2 ? INT_MAX : nums2[m2]);
36
37    return (c1 + c2) * 0.5;
38}

1                      ## JavaScript Solution

1
2javascript
3var findMedianSortedArrays = function(nums1, nums2) {
4    let combinedArray = nums1.concat(nums2).sort((a, b) => a - b);
5    let median;
6    let length = combinedArray.length;
7    let mid = Math.floor(length / 2);
8    
9    if (length % 2 === 0) {
10        median = (combinedArray[mid-1] + combinedArray[mid]) / 2;
11    } else {
12        median = combinedArray[mid];
13    } 
14    return median;
15};
16
17let nums1 = [1, 3];
18let nums2 = [2];
19console.log(findMedianSortedArrays(nums1, nums2)); // Output: 2.0
20
21let nums1 = [1, 2];
22let nums2 = [3, 4];
23console.log(findMedianSortedArrays(nums1, nums2)); // Output: 2.5

In this JS solution, we've used a straightforward and efficient way to solve the problem.

First, we merge the arrays using the concat() method, sort() method is then used to sort the numbers in ascending order.

Next, we calculate the median by checking the array length.

• If the array size is even, the median is the average of the two middle numbers. Here, since the array is 0-indexed, those will be located at mid-1 and mid, hence (combinedArray[mid-1] + combinedArray[mid]) / 2.
• If the array size is odd, the median is the middle number, found at index mid.

Finally, we return the median.

This approach gets the job done but is not the most efficient. The sort operation can take up to O(n log(n)) time for unsorted arrays. To optimize it further, algorithms such as binary search can be used, which are more involved but will offer better time complexity (i.e., logarithmic time complexity).

In a scenario where the input arrays are extremely large, using a more efficient algorithm like binary search-based might indeed be an optimal solution.