Median of Two Sorted Arrays

LeetCode 4 | Difficulty: Hard

Hard

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

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.

Constraints:

- `nums1.length == m`

- `nums2.length == n`

- `0 <= m <= 1000`

- `0 <= n <= 1000`

- `1 <= m + n <= 2000`

- `-10^6 <= nums1[i], nums2[i] <= 10^6`

Topics: Array, Binary Search, Divide and Conquer

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 104 ms)

Metric	Value
Runtime	104 ms
Memory	41.4 MB
Date	2021-12-25

Solution

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
      int n1 = nums1.Length;
    int n2 = nums2.Length;
    
    
    if(n2<n1) return FindMedianSortedArrays(nums2, nums1);
    int lo=0, hi = n1;
    while(lo <= hi)
    {
        int cut1 = (lo+hi)/2;
        int cut2 = (n1+n2)/2-cut1;
        
        double l1 = (cut1 == 0) ? Int32.MinValue : nums1[cut1-1];
        double l2 = (cut2 == 0) ? Int32.MinValue : nums2[cut2 - 1];
        double r1 = (cut1 == n1 ) ? Int32.MaxValue : nums1[cut1];
        double r2 = (cut2 == n2) ? Int32.MaxValue : nums2[cut2];
        
        if(l1 > r2) hi = cut1-1;
        else if (l2 > r1) lo = cut1+1;
        else return (n1+n2)%2 != 0 ? Math.Min(r1,r2) : (Math.Max(l1,l2) + Math.Min(r1,r2)) / 2;
    }
    return -1;  
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Precisely define what the left and right boundaries represent, and the loop invariant.