Back to LeetCode Series

LeetCode #4: Median of Two Sorted Arrays

Find the median of two sorted arrays in O(log(min(m,n))) time using binary search on partitions.

Difficulty: HardPattern: Binary SearchTime: 10 min read

🎯 What is a Median?

The median is the middle value in a sorted list:

  • If the list has odd length: median = middle element
  • If even length: median = average of two middle elements

Odd: [1, 2, 3, 4, 5] → median = 3

Even: [1, 2, 3, 4] → median = (2 + 3)/2 = 2.5

The Problem

Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays.

You must write an algorithm that runs in O(log(min(m,n))) time.

Examples

nums1: [1, 3]  nums2: [2]   → Median: 2  (merged array = [1,2,3] → median = 2)

nums1: [1, 2]  nums2: [3, 4]   → Median: 2.5  (merged array = [1,2,3,4] → median = (2 + 3)/2 = 2.5)

nums1: [0, 0]  nums2: [0, 0]   → Median: 0  (All zeros → median = 0)

❌ Brute Force: Merge & Find Median

The simplest way: merge both arrays, sort them, then find the median.

js
1
2
3
4
5
6
7
8
9
10
function findMedianSortedArrays(nums1, nums2) {
  const merged = [...nums1, ...nums2].sort((a, b) => a - b);
  const mid = Math.floor(merged.length / 2);

  if (merged.length % 2 === 0) {
    return (merged[mid - 1] + merged[mid]) / 2;
  } else {
    return merged[mid];
  }
}

✅ Simple, but ❌ O((m+n) log(m+n)) time — too slow!

✅ Optimized: Binary Search on Partition

We can't merge the arrays, but we can use binary search to find the correct split.

🔑 Key Insight

The median divides the combined array into two halves:

  • Left half: all values ≤ median
  • Right half: all values ≥ median

We want to split nums1 and nums2 such that:
max(left) ≤ min(right)

How It Works

  1. We binary search on the smaller array to find the correct partition
  2. For each partition in nums1, we compute the matching one in nums2
  3. We check if maxLeft ≤ minRight
  4. If yes → we found the median
  5. If no → adjust the binary search bounds
js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the smaller array
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }

  const m = nums1.length;
  const n = nums2.length;
  let left = 0;
  let right = m;

  while (left <= right) {
    const partition1 = Math.floor((left + right) / 2);
    const partition2 = Math.floor((m + n + 1) / 2) - partition1;

    const maxLeft1 = partition1 === 0 ? -Infinity : nums1[partition1 - 1];
    const minRight1 = partition1 === m ? Infinity : nums1[partition1];

    const maxLeft2 = partition2 === 0 ? -Infinity : nums2[partition2 - 1];
    const minRight2 = partition2 === n ? Infinity : nums2[partition2];

    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      // Correct partition found
      if ((m + n) % 2 === 0) {
        return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
      } else {
        return Math.max(maxLeft1, maxLeft2);
      }
    } else if (maxLeft1 > minRight2) {
      right = partition1 - 1; // too far right in nums1
    } else {
      left = partition1 + 1; // too far left in nums1
    }
  }

  throw new Error("Arrays are not sorted");
}

💡 Why O(log(min(m,n)))? We binary search on the smaller array — so the number of steps is logarithmic in the smaller size.

🌍 Real-World Applications

This "find median without merging" idea is used in systems where data is large or distributed.

📊 Data Analytics

When analyzing logs or user behavior across servers, you might have sorted data on each machine. Finding the global median without transferring all data saves bandwidth and time.

💾 Database Systems

Distributed databases often keep sorted indexes. To compute statistics (like median), they use partitioning techniques instead of full merges.

📡 Network Monitoring

Routers collect timestamped packets in sorted order. To find median latency across links, they use divide-and-conquer methods like this one.

📈 Financial Systems

Stock exchanges process sorted price feeds. Calculating median prices across markets efficiently is critical — and uses similar partitioning logic.

🔑 Why This Matters: This problem teaches that binary searchisn’t just for finding values, it can be used to find optimal partitions in complex data.

Summary

This problem teaches a powerful idea: binary search doesn't just work on arrays — it can work on "partitions". By ensuring correct left/right splits, we find the median without merging.

View All Challenges