ArrayProblem 36 of 36

Median of 2 sorted arrays of different size

Brute Force
Time: O(m + n)
Space: O(m + n)
Optimal
Time: O(log(min(m, n)))
Space: O(1)

Problem Statement

Given two sorted arrays of different sizes, find the median of the combined sorted array. This is a generalization of the equal size problem.

Example:

  • Input: arr1 = [1, 3], arr2 = [2]
  • Output: 2.0
  • Explanation: Merged array: [1, 2, 3]. Median = 2.

Example 2:

  • Input: arr1 = [1, 2], arr2 = [3, 4]
  • Output: 2.5
  • Explanation: Merged array: [1, 2, 3, 4]. Median = (2 + 3) / 2 = 2.5.

Approach 1: Brute Force (Merge Arrays)

Intuition

Merge both arrays and find the median directly.

Algorithm

  1. Merge both sorted arrays
  2. If total length is odd, return middle element
  3. If even, return average of two middle elements
java
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merged = new int[m + n];
        
        int i = 0, j = 0, k = 0;
        
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];
        
        int total = m + n;
        if (total % 2 == 1) {
            return merged[total / 2];
        }
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    }
}

Complexity Analysis

  • Time Complexity: O(m + n) - Merge both arrays
  • Space Complexity: O(m + n) - Store merged array

Approach 2: Count Without Full Merge

Intuition

We only need to find the middle element(s), so count up to that position.

Algorithm

  1. Use two pointers to count elements
  2. Stop when we reach the middle position(s)
  3. Return appropriate median value
java
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        
        int i = 0, j = 0;
        int prev = 0, curr = 0;
        
        for (int count = 0; count <= total / 2; count++) {
            prev = curr;
            
            if (i == m) {
                curr = nums2[j++];
            } else if (j == n) {
                curr = nums1[i++];
            } else if (nums1[i] <= nums2[j]) {
                curr = nums1[i++];
            } else {
                curr = nums2[j++];
            }
        }
        
        if (total % 2 == 1) {
            return curr;
        }
        return (prev + curr) / 2.0;
    }
}

Complexity Analysis

  • Time Complexity: O(m + n) - Count to middle
  • Space Complexity: O(1) - Only constant extra space

Approach 3: Optimal - Binary Search

Intuition

Binary search on the smaller array to find correct partition. The partition divides combined arrays into two halves where all left elements are smaller than all right elements.

Algorithm

  1. Always binary search on smaller array (ensures O(log min(m,n)))
  2. Find partition in arr1, calculate corresponding partition in arr2
  3. Check if partition is valid (left elements ≤ right elements)
  4. Adjust binary search bounds based on comparison
java
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is smaller
        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;
            
            // Handle edge cases
            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
            
            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];
            
            // Check if we found the correct partition
            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;
            }
        }
        
        return 0.0;
    }
}

Complexity Analysis

  • Time Complexity: O(log(min(m, n))) - Binary search on smaller array
  • Space Complexity: O(1) - Only constant extra space

Understanding the Binary Search Approach

Partition Concept

nums1: [... maxLeftX | minRightX ...] nums2: [... maxLeftY | minRightY ...] Merged: [... maxLeftX, maxLeftY | minRightX, minRightY ...] Left Half | Right Half

Key Conditions

  1. Left half size = (m + n + 1) / 2 (handles both odd and even)
  2. Valid partition: maxLeftX ≤ minRightY AND maxLeftY ≤ minRightX
  3. Median for odd: max(maxLeftX, maxLeftY)
  4. Median for even: (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2

Why Search on Smaller Array?

  • Ensures partition in larger array is always valid (0 ≤ partitionY ≤ n)
  • Reduces time complexity to O(log(min(m, n)))

Key Takeaways

  1. Classic hard problem - LeetCode #4, frequently asked in interviews
  2. Binary search on partition - Key insight for O(log n) solution
  3. Always search smaller array - Ensures valid partition in larger array
  4. Handle odd/even total - Different median calculation
  5. Edge cases with infinity - Handle empty partitions with INT_MIN/INT_MAX
  6. Partition math - partitionY = (m + n + 1) / 2 - partitionX ensures equal halves
Previous
Median of 2 sorted arrays of equal size