Median of Two Sorted Arrays

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approach
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

Given sorted arrays nums1 and nums2, return median of combined sorted order.

Example 1:
nums1=[1,3], nums2=[2]
median=2.0

Example 2:
nums1=[1,2], nums2=[3,4]
median=2.5

🎯 Real-World Analogy

Balancing Two Sorted Lines

Cut both lines so left side has exactly half the people, and every left-side value is <= every right-side value.

💡 Key Insights

Binary search on smaller array only.
Choose partition i in A and j in B so left size is half.
Valid partition when Aleft <= Bright and Bleft <= Aright.
Then median is max(left) for odd total, average of max(left)/min(right) for even total.

💻 Solution Approach

Time: O(log(min(m,n))) | Space: O(1)

Python Implementation

from typing import List


def find_median_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A

    m, n = len(A), len(B)
    total = m + n
    half = total // 2

    left, right = 0, m
    while True:
        i = (left + right) // 2
        j = half - i

        Aleft = A[i - 1] if i > 0 else float("-inf")
        Aright = A[i] if i < m else float("inf")
        Bleft = B[j - 1] if j > 0 else float("-inf")
        Bright = B[j] if j < n else float("inf")

        if Aleft <= Bright and Bleft <= Aright:
            if total % 2 == 1:
                return float(min(Aright, Bright))
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:
            right = i - 1
        else:
            left = i + 1

JavaScript Implementation

function findMedianSortedArrays(nums1, nums2) {
  let A = nums1;
  let B = nums2;
  if (A.length > B.length) {
    [A, B] = [B, A];
  }

  const m = A.length;
  const n = B.length;
  const total = m + n;
  const half = Math.floor(total / 2);

  let left = 0;
  let right = m;

  while (true) {
    const i = Math.floor((left + right) / 2);
    const j = half - i;

    const Aleft = i > 0 ? A[i - 1] : -Infinity;
    const Aright = i < m ? A[i] : Infinity;
    const Bleft = j > 0 ? B[j - 1] : -Infinity;
    const Bright = j < n ? B[j] : Infinity;

    if (Aleft <= Bright && Bleft <= Aright) {
      if (total % 2 === 1) return Math.min(Aright, Bright);
      return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2;
    } else if (Aleft > Bright) {
      right = i - 1;
    } else {
      left = i + 1;
    }
  }
}

🔍 Step-by-Step Walkthrough

A=[1,2], B=[3,4], total=4, half=2:

Try i=1 => j=1. Aleft=1, Aright=2, Bleft=3, Bright=4.
Bleft > Aright, move i right.
i=2 => j=0 valid partition. maxLeft=2, minRight=3.
Even total => median=(2+3)/2=2.5.

⚡ Complexity Analysis

Time: O(log(min(m,n))) due binary search on smaller array.

Space: O(1).

🔧 Edge Cases

One array empty
Both arrays size 1
Odd vs even combined length
Highly unbalanced sizes
Negative values and duplicates

🧪 Test Cases

[1,3] + [2] => 2.0
[1,2] + [3,4] => 2.5
[] + [1] => 1.0
[0,0] + [0,0] => 0.0

💼 Interview Tips

State partition invariants clearly before coding.
Always search smaller array to keep complexity bound.
Use +/-Infinity guards to avoid branch explosion.

🎓 Key Takeaways

This is a boundary-partition binary search problem, not a merge problem.
Correctness comes from left/right partition ordering constraints.

← Back to All Algorithms