4. Median of Two Sorted Arrays – Leetcode Solutions

June 3, 2024

Table of Contents

Description:

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)).

Examples:

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.

Solution in Python:

To find the median of two sorted arrays with a run time complexity of O(log⁡(m+n)), we can use a binary search approach. The key idea is to partition the two arrays in such a way that the elements on the left side of the partition are less than or equal to the elements on the right side of the partition.

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Ensure nums1 is the smaller array to make binary search faster
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        low, high = 0, m
        
        while low <= high:
            partitionX = (low + high) // 2
            partitionY = (m + n + 1) // 2 - partitionX
            
            maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
            maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
            
            minX = float('inf') if partitionX == m else nums1[partitionX]
            minY = float('inf') if partitionY == n else nums2[partitionY]
            
            # Check if we have partitioned the arrays correctly
            if maxX <= minY and maxY <= minX:
                # Check if the total number of elements is even or odd
                if (m + n) % 2 == 0:
                    return (max(maxX, maxY) + min(minX, minY)) / 2
                else:
                    return max(maxX, maxY)
            elif maxX > minY:
                # Move towards left in nums1
                high = partitionX - 1
            else:
                # Move towards right in nums1
                low = partitionX + 1
        
        raise ValueError("Input arrays are not sorted")

# Example usage:
sol = Solution()
print(sol.findMedianSortedArrays([1, 3], [2]))  # Output: 2.0
print(sol.findMedianSortedArrays([1, 2], [3, 4]))  # Output: 2.5

Explanation:

Ensuring nums1 is the smaller array:
- This is done to make sure the binary search is performed on the smaller array for efficiency.
Binary Search Setup:
- We perform a binary search on the smaller array nums1 with low starting at 0 and high starting at the length of nums1.
Partitions:
- partitionX and partitionY represent the positions where the arrays are divided.
- partitionX is the middle index of the current search range in nums1.
- partitionY is calculated such that the left side of the partition has the same number of elements as the right side (or one more if the total number of elements is odd).
Max and Min Values:
- maxX and maxY are the maximum elements on the left side of the partitions.
- minX and minY are the minimum elements on the right side of the partitions.
- Edge cases are handled by setting maxX and maxY to negative infinity if the partition is at the beginning of an array and minX and minY to positive infinity if the partition is at the end of an array.
Correct Partition Check:
- If the maximum element on the left side of nums1 is less than or equal to the minimum element on the right side of nums2 and vice versa, the correct partition is found.
- If the total number of elements is even, the median is the average of the maximum element on the left side and the minimum element on the right side.
- If the total number of elements is odd, the median is the maximum element on the left side.
Adjusting the Search Range:
- If maxX is greater than minY, we move the partition in nums1 to the left.
- If maxY is greater than minX, we move the partition in nums1 to the right.

By using this approach, we achieve the desired O(log⁡(m+n)) time complexity.

Solution in Javascript:

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // Ensure nums1 is the smaller array to make the binary search faster
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    let m = nums1.length;
    let n = nums2.length;
    let low = 0;
    let high = m;

    while (low <= high) {
        let partitionX = Math.floor((low + high) / 2);
        let partitionY = Math.floor((m + n + 1) / 2) - partitionX;

        let maxX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
        let maxY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];

        let minX = (partitionX === m) ? Infinity : nums1[partitionX];
        let minY = (partitionY === n) ? Infinity : nums2[partitionY];

        // Check if we have partitioned the arrays correctly
        if (maxX <= minY && maxY <= minX) {
            // Check if the total number of elements is even or odd
            if ((m + n) % 2 === 0) {
                return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
            } else {
                return Math.max(maxX, maxY);
            }
        } else if (maxX > minY) {
            // Move towards left in nums1
            high = partitionX - 1;
        } else {
            // Move towards right in nums1
            low = partitionX + 1;
        }
    }

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

// Example usage:
console.log(findMedianSortedArrays([1, 3], [2])); // Output: 2.0
console.log(findMedianSortedArrays([1, 2], [3, 4])); // Output: 2.5

Solution in Java:

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array to make the binary search faster
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int low = 0;
        int high = m;

        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (m + n + 1) / 2 - partitionX;

            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];

            int minX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
            int minY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];

            // Check if we have partitioned the arrays correctly
            if (maxX <= minY && maxY <= minX) {
                // Check if the total number of elements is even or odd
                if ((m + n) % 2 == 0) {
                    return ((double)Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
                } else {
                    return (double)Math.max(maxX, maxY);
                }
            } else if (maxX > minY) {
                // Move towards left in nums1
                high = partitionX - 1;
            } else {
                // Move towards right in nums1
                low = partitionX + 1;
            }
        }

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findMedianSortedArrays(new int[]{1, 3}, new int[]{2})); // Output: 2.0
        System.out.println(sol.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4})); // Output: 2.5
    }
}

Solution in C#:

C#

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array to make the binary search faster
        if (nums1.Length > nums2.Length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.Length;
        int n = nums2.Length;
        int low = 0;
        int high = m;

        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (m + n + 1) / 2 - partitionX;

            int maxX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
            int maxY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];

            int minX = (partitionX == m) ? int.MaxValue : nums1[partitionX];
            int minY = (partitionY == n) ? int.MaxValue : nums2[partitionY];

            // Check if we have partitioned the arrays correctly
            if (maxX <= minY && maxY <= minX) {
                // Check if the total number of elements is even or odd
                if ((m + n) % 2 == 0) {
                    return ((double)Math.Max(maxX, maxY) + Math.Min(minX, minY)) / 2;
                } else {
                    return (double)Math.Max(maxX, maxY);
                }
            } else if (maxX > minY) {
                // Move towards left in nums1
                high = partitionX - 1;
            } else {
                // Move towards right in nums1
                low = partitionX + 1;
            }
        }

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

}

4. Median of Two Sorted Arrays – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

98. Validate Binary Search Tree – Leetcode Solutions

105. Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solutions

32. Longest Valid Parentheses – Leetcode Solutions

341. Flatten Nested List Iterator – Leetcode Solutions

414. Third Maximum Number – Leetcode Solutions

355. Design Twitter – Leetcode Solutions

282. Expression Add Operators – Leetcode Solutions

4. Median of Two Sorted Arrays – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular