Code Implementation

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        # Ensure nums1 is the smaller array
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        total = m + n
        half = total // 2

        left, right = 0, m
        while True:
            i = (left + right) // 2  # Partition in nums1
            j = half - i             # Partition in nums2

            nums1Left = nums1[i-1] if i > 0 else float('-inf')
            nums1Right = nums1[i] if i < m else float('inf')
            nums2Left = nums2[j-1] if j > 0 else float('-inf')
            nums2Right = nums2[j] if j < n else float('inf')

            if nums1Left <= nums2Right and nums2Left <= nums1Right:
                # Found correct partition
                if total % 2:
                    return min(nums1Right, nums2Right)
                return (max(nums1Left, nums2Left) + min(nums1Right, nums2Right)) / 2
            elif nums1Left > nums2Right:
                right = i - 1
            else:
                left = i + 1
      

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2, nums1);

        int m = nums1.size(), n = nums2.size();
        int total = m + n;
        int half = total / 2;
        int left = 0, right = m;

        while (true) {
            int i = (left + right) / 2;
            int j = half - i;

            int nums1Left = (i > 0) ? nums1[i-1] : INT_MIN;
            int nums1Right = (i < m) ? nums1[i] : INT_MAX;
            int nums2Left = (j > 0) ? nums2[j-1] : INT_MIN;
            int nums2Right = (j < n) ? nums2[j] : INT_MAX;

            if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
                if (total % 2)
                    return std::min(nums1Right, nums2Right);
                return (std::max(nums1Left, nums2Left) + std::min(nums1Right, nums2Right)) / 2.0;
            } else if (nums1Left > nums2Right) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
    }
};
      

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);

        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int half = total / 2;
        int left = 0, right = m;

        while (true) {
            int i = (left + right) / 2;
            int j = half - i;

            int nums1Left = (i > 0) ? nums1[i-1] : Integer.MIN_VALUE;
            int nums1Right = (i < m) ? nums1[i] : Integer.MAX_VALUE;
            int nums2Left = (j > 0) ? nums2[j-1] : Integer.MIN_VALUE;
            int nums2Right = (j < n) ? nums2[j] : Integer.MAX_VALUE;

            if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
                if (total % 2 == 1)
                    return Math.min(nums1Right, nums2Right);
                return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2.0;
            } else if (nums1Left > nums2Right) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
    }
}
      

var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    let m = nums1.length, n = nums2.length;
    let total = m + n;
    let half = Math.floor(total / 2);
    let left = 0, right = m;

    while (true) {
        let i = Math.floor((left + right) / 2);
        let j = half - i;

        let nums1Left = (i > 0) ? nums1[i-1] : -Infinity;
        let nums1Right = (i < m) ? nums1[i] : Infinity;
        let nums2Left = (j > 0) ? nums2[j-1] : -Infinity;
        let nums2Right = (j < n) ? nums2[j] : Infinity;

        if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
            if (total % 2 === 1) {
                return Math.min(nums1Right, nums2Right);
            }
            return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2;
        } else if (nums1Left > nums2Right) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }
};
      

Problem Description

You are given two sorted arrays, nums1 and nums2, with lengths m and n respectively. The task is to find the median of the two sorted arrays, as if they were merged into one sorted array. The overall run time complexity should be O(log (m+n)).

• Both nums1 and nums2 are sorted in non-decreasing order.
• The arrays can have different lengths, and may be empty.
• There is exactly one solution for every input.
• Elements can be reused; you do not remove them from the input arrays.

Thought Process

At first glance, the problem seems to require merging the two arrays and then finding the median. This brute-force approach is simple: merge, sort, and pick the middle element(s). However, this takes O(m+n) time and uses extra space, which does not meet the required O(log (m+n)) time complexity.

To optimize, we need to avoid full merging. Since both arrays are already sorted, we can use a binary search. The key insight is to partition the arrays such that the left half contains the same number of elements as the right half, and all elements on the left are less than or equal to those on the right. This allows us to compute the median directly without merging.

By always binary searching the smaller array, we reduce the search space and ensure efficiency.

Solution Approach

To find the median in O(log (m+n)) time, we use the following approach:

1. Identify the smaller array: Always binary search on the shorter array to keep the search space minimal.
2. Binary search for the correct partition:
   • Let i be the partition index in nums1 and j in nums2, such that i + j = (m + n) // 2.
   • At each step, check if the left partition’s largest value is less than or equal to the right partition’s smallest value in both arrays.
   • If not, move the binary search window accordingly.
3. Check partition correctness:
   • If nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i], you’ve found the correct partition.
   • Otherwise, adjust the binary search range: if nums1[i-1] > nums2[j], move left; else, move right.
4. Compute the median:
   • If the total number of elements is odd, the median is the minimum of the right side.
   • If even, the median is the average of the maximum of the left sides and the minimum of the right sides.
5. Edge cases: Use float('-inf') or float('inf') (or their language equivalents) when the partition is at the start or end of an array, to handle empty sides gracefully.

Example Walkthrough

Let’s consider nums1 = [1, 3] and nums2 = [2]:

• Total elements: 3 (odd), so median is the second element.
• Binary search on the smaller array: nums1.
• First partition:
  • i = 1 (partition nums1 at 1), j = 1 (partition nums2 at 1)
  • nums1Left = 1, nums1Right = 3
  • nums2Left = 2, nums2Right = inf (since j is at the end)
• Check partitions:
  • nums1Left (1) <= nums2Right (inf) is true
  • nums2Left (2) <= nums1Right (3) is true
  So, correct partition found.
• Median: Since total is odd, pick min(nums1Right, nums2Right) = min(3, inf) = 3.

Thus, the median is 2 (since in the merged array [1,2,3], it is the middle value).

Time and Space Complexity

• Brute-force approach: Merge and sort takes O(m+n) time and O(m+n) space.
• Optimized approach (binary search): Time complexity is O(log(min(m, n))) because we binary search over the smaller array. Space complexity is O(1) since we only use a few pointers and variables.

The binary search is efficient because it reduces the search space by half each iteration, and only examines the smaller of the two arrays.

Summary

The key insight is to use binary search to partition the two sorted arrays such that the left and right partitions together form a valid split for finding the median. By always searching the smaller array, we ensure efficiency and avoid unnecessary work. This approach is elegant because it transforms a seemingly complex merge problem into a simple search for the correct partition, achieving optimal time and space complexity.