Pseudo-code:

text
function bruteForce(nums1, nums2):
    merged = []
    while nums1 has elements or nums2 has elements:
        add smaller head element to merged
    
    mid = length(merged) / 2
    if length(merged) is odd:
        return merged[mid]
    else:
        return (merged[mid-1] + merged[mid]) / 2

Complexity Analysis: The time complexity is O(m + n) because we must iterate through every element in both arrays to merge them. The space complexity is O(m + n) to store the merged array.

Why it fails: While this approach produces the correct answer, it violates the strict time complexity constraint of O(log (m+n)) required by the problem statement. In a technical interview, implementing an O(m+n) solution when a logarithmic solution is requested is considered suboptimal.

Core Insight for Median of Two Sorted Arrays

The core insight is that we do not need to merge the arrays to determine the median. We only need to ensure that the set of elements on the "left" side of a partition is smaller than or equal to the set of elements on the "right" side.

Let's assume we partition nums1 at index i and nums2 at index j. If the partition is valid, the following must hold:

1. The number of elements in the left halves (from both arrays) equals the number of elements in the right halves (plus one if the total length is odd).
2. Every element in the left part of nums1 is less than or equal to every element in the right part of nums2.
3. Every element in the left part of nums2 is less than or equal to every element in the right part of nums1.

Since the total number of elements required in the left half is fixed ((m + n + 1) / 2), the position of cut j in nums2 is entirely dependent on the position of cut i in nums1. This implies we only need to binary search for the correct index i.

Visual Description: Imagine nums1 and nums2 aligned horizontally. We introduce a vertical "cut" through nums1 and a corresponding cut through nums2.

• If the element immediately to the left of the cut in nums1 is greater than the element immediately to the right of the cut in nums2, our cut in nums1 is too far to the right. We must move the binary search range to the left.
• Conversely, if the element to the left in nums2 is greater than the element to the right in nums1, our cut in nums1 is too far to the left. We must move the search range to the right.

Execution Flow

Let's trace nums1 = [1, 3] and nums2 = [2].

• nums1 length is 2, nums2 length is 1. Swap so nums1 is [2] (size 1) and nums2 is [1, 3] (size 2).
• m = 1, n = 2. Total elements = 3. Halfway point = (1 + 2 + 1) // 2 = 2.
• Iteration 1:
  • low = 0, high = 1.
  • partitionX = (0 + 1) // 2 = 0.
  • partitionY = 2 - 0 = 2.
  • maxLeftX = $-\infty$ (index 0), minRightX = 2 (index 0).
  • maxLeftY = 3 (index 1), minRightY = $+\infty$ (index 2).
  • Check: Is maxLeftX ($-\infty$) $\le$ minRightY ($+\infty$)? Yes.
  • Check: Is maxLeftY (3) $\le$ minRightX (2)? No.
  • Logic: maxLeftY > minRightX, so we need more elements from nums1. Move right. low = partitionX + 1 = 1.
• Iteration 2:
  • low = 1, high = 1.
  • partitionX = 1.
  • partitionY = 2 - 1 = 1.
  • maxLeftX = 2, minRightX = $+\infty$.
  • maxLeftY = 1, minRightY = 3.
  • Check: Is 2 $\le$ 3? Yes.
  • Check: Is 1 ? Yes.

Proof of Correctness

The algorithm maintains the invariant that the total number of elements on the left side of the partition (from both arrays combined) is always (m + n + 1) / 2.

The binary search moves the partition in nums1 left or right. As partitionX increases (moves right), partitionY decreases (moves left). This causes maxLeftX to increase (or stay same) and minRightY to decrease (or stay same). Because the arrays are sorted, there is a unique point where the cross-over condition maxLeftX <= minRightY and maxLeftY <= minRightX is satisfied. This unique point represents the correct sorted order merge without physically merging.

Reference Implementation

C++ Solution for LeetCode 4

cpp
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // Ensure nums1 is the smaller array to optimize binary search
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.size();
        int n = nums2.size();
        int low = 0, high = m;

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

            // Handle edge cases with infinity
            double maxLeftX = (partitionX == 0) ? -1e18 : nums1[partitionX - 1];
            double minRightX = (partitionX == m) ? 1e18 : nums1[partitionX];

            double maxLeftY = (partitionY == 0) ? -1e18 : nums2[partitionY - 1];
            double minRightY = (partitionY == n) ? 1e18 : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                // Correct partition found
                if ((m + n) % 2 == 0) {
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0;
                } else {
                    return max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                // We are too far right in nums1
                high = partitionX - 1;
            } else {
                // We are too far left in nums1
                low = partitionX + 1;
            }
        }
        
        throw invalid_argument("Input arrays are not sorted or invalid.");
    }
};

Java Solution for LeetCode 4

java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure binary search happens on the smaller array
        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;

            // Use Integer.MIN_VALUE/MAX_VALUE for edge cases
            // Note: Using double for calculation to avoid overflow issues if values are large
            double maxLeftX = (partitionX == 0) ? Double.NEGATIVE_INFINITY : nums1[partitionX - 1];
            double minRightX = (partitionX == m) ? Double.POSITIVE_INFINITY : nums1[partitionX];

            double maxLeftY = (partitionY == 0) ? Double.NEGATIVE_INFINITY : nums2[partitionY - 1];
            double minRightY = (partitionY == n) ? Double.POSITIVE_INFINITY : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
                } else {
                    return Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        
        throw new IllegalArgumentException("Arrays not sorted");
    }
}

Python Solution for LeetCode 4

python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Ensure nums1 is the smaller array
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(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
            
            # Handle edges using infinity
            maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
            minRightX = float('inf') if partitionX == m else nums1[partitionX]
            
            maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
            minRightY = float('inf') if partitionY == n else nums2[partitionY]
            
            if maxLeftX <= minRightY and maxLeftY <= minRightX:
                # Correct partition found
                if (m + n) % 2 == 0:
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
                else:
                    return max(maxLeftX, maxLeftY)
            elif maxLeftX > minRightY:
                high = partitionX - 1
            else:
                low = partitionX + 1

Q: Why is my answer slightly off for even-length combined arrays?

• Mistake: Returning an integer division instead of float division, or picking the wrong elements to average.
• Why: For even lengths, the median is the average of the largest element on the left side and the smallest element on the right side.
• Consequence: Incorrect return value. Ensure you calculate (max(lefts) + min(rights)) / 2.0.