LeetCode #4 - Median of Two Sorted Arrays

Hello, coding enthusiasts! 👋 Today, we’re going to unravel another challenging problem from LeetCode: “Median of Two Sorted Arrays”.

Problem Statement

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

The overall run time complexity should be O(log (m+n)).

Constraints

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

Analysis

The task is to find the median of two sorted arrays. The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Approach

The most efficient approach to solve this problem is to use binary search. Here’s how it works:

Find the shorter array: If nums1 is shorter than nums2, swap them.
Initialize binary search: Set the start and end of the binary search to 0 and m respectively, where m is the length of the shorter array.
Perform binary search: Find the partition point in the shorter array such that elements on the left side are smaller than elements on the right side in both arrays.
Calculate the median: If the total length of the arrays is odd, the median is the maximum of the leftmost elements of both partitions. If it’s even, the median is the average of the maximum of the leftmost elements and the minimum of the rightmost elements.

Time Complexity

The time complexity for this approach is O(log(min(m, n))), where m and n are the lengths of the two arrays. This is because we’re performing binary search on the shorter array.

Space Complexity

The space complexity is O(1), as we are using a constant amount of space.

Code

Here’s the Python and JavaScript code for this approach:

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        x, y = len(nums1), len(nums2)
        start = 0
        end = x

        while start <= end:
            partitionX = (start + end) // 2
            partitionY = (x + y + 1) // 2 - partitionX

            maxLeftX = float("-inf") if partitionX == 0 else nums1[partitionX - 1]
            minRightX = float("inf") if partitionX == x else nums1[partitionX]

            maxLeftY = float("-inf") if partitionY == 0 else nums2[partitionY - 1]
            minRightY = float("inf") if partitionY == y else nums2[partitionY]

            if maxLeftX <= minRightY and maxLeftY <= minRightX:
                if (x + y) % 2 == 0:
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
                else:
                    return max(maxLeftX, maxLeftY)

            elif maxLeftX > minRightY:
                end = partitionX - 1

            else:
                start = partitionX + 1

        raise Exception("Input arrays are not sorted")

JavaScript

var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];

    let x = nums1.length;
    let y = nums2.length;
    let start = 0;
    let end = x;

    while (start <= end) {
        let partitionX = Math.floor((start + end) / 2);
        let partitionY = Math.floor((x + y + 1) / 2) - partitionX;

        let maxLeftX = (partitionX === 0) ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
        let minRightX = (partitionX === x) ? Number.POSITIVE_INFINITY : nums1[partitionX];

        let maxLeftY = (partitionY === 0) ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
        let minRightY = (partitionY === y) ? Number.POSITIVE_INFINITY : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            end = partitionX - 1;
        } else {
            start = partitionX + 1;
        }
    }

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

Conclusion

In this post, we tackled the “Median of Two Sorted Arrays” problem from LeetCode using binary search. This solution has a time complexity of O(log(min(m, n))) and a space complexity of O(1).

Happy coding 😄!

Learn More:

LeetCode #4 – Median of Two Sorted Arrays