Median of Two Sorted Arrays

Hardbinary-searcharraydivide-and-conquer
Category: Binary Search
Companies that ask this question:
GoogleAmazonMicrosoftFacebookApple
LeetCode →NeetCode →

Approach

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

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.

Intuition

The brute force approach of merging arrays takes O(m+n). To achieve O(log(m+n)), we use binary search on partition position.

Key Insight: The median divides an array into two equal halves. For two arrays, we need to find a partition such that:

  • Left half of combined array = Right half
  • All elements in left ≤ All elements in right

We binary search on the smaller array to find the correct partition.

Pattern Recognition

This is Advanced Binary Search (Partition-based) with:

  • Two sorted arrays
  • Find statistical property (median)
  • O(log min(m,n)) optimal solution
  • Partition both arrays simultaneously

Approach

  1. Ensure nums1 is smaller: If m > n, swap arrays (search on smaller)

  2. Binary Search on Partition:

    • left = 0, right = m
    • partition1 = mid position in nums1
    • partition2 = (m+n+1)/2 - partition1 (ensures equal halves)

  3. Check Valid Partition:

    • maxLeft1 = largest element in left half of nums1
    • minRight1 = smallest element in right half of nums1
    • maxLeft2, minRight2 = same for nums2
    • Valid if: maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1

  4. Calculate Median:

    • Odd total length: max(maxLeft1, maxLeft2)
    • Even total length: (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2

  5. Adjust Search:

    • If maxLeft1 > minRight2: Move left (partition1 too large)
    • Else: Move right

Edge Cases

  • One array empty
  • Arrays of very different sizes
  • All elements in nums1 < all in nums2
  • Overlapping arrays

Complexity Analysis

  • Time Complexity: O(log min(m, n))

    • Binary search on smaller array

  • Space Complexity: O(1)

    • Only using variables for partitions

Solution

java
1class Solution {
2    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3        // Ensure nums1 is the smaller array
4        if (nums1.length > nums2.length) {
5            return findMedianSortedArrays(nums2, nums1);
6        }
7
8        int m = nums1.length;
9        int n = nums2.length;
10        int left = 0;
11        int right = m;
12
13        while (left <= right) {
14            int partition1 = (left + right) / 2;
15            int partition2 = (m + n + 1) / 2 - partition1;
16
17            // Handle edge cases for partition boundaries
18            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
19            int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
20
21            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
22            int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
23
24            // Check if we found the correct partition
25            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
26                // Found correct partition
27                if ((m + n) % 2 == 0) {
28                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
29                } else {
30                    return Math.max(maxLeft1, maxLeft2);
31                }
32            } else if (maxLeft1 > minRight2) {
33                // partition1 is too large, move left
34                right = partition1 - 1;
35            } else {
36                // partition1 is too small, move right
37                left = partition1 + 1;
38            }
39        }
40
41        throw new IllegalArgumentException("Input arrays are not sorted");
42    }
43}
44
Loading visualizer...