How do you solve Median of Two Sorted Arrays?

Use binary search on the smaller array to find the partition index i. Calculate j = half - i - 2 to partition the second array accordingly. Compare boundary elements Aleft, Aright, Bleft, Bright to check if the partition is valid. If valid, compute the median based on total length parity. Otherwise, adjust the binary search range by moving left or right pointers. This approach guarantees logarithmic time complexity and constant space.

Median of Two Sorted Arrays

Q: What is the time complexity of Median of Two Sorted Arrays?

O(log(min(m, n))). The binary search is performed on the smaller array, which has length min(m, n). Each iteration halves the search space, leading to logarithmic time complexity.

Q: What pattern does Median of Two Sorted Arrays use?

The Pattern: Modified Binary Search (Partitioning Technique) The Heuristic: When searching for a median or kth element across two sorted arrays, transform the problem into finding a partition point that balances elements on both sides, then use binary search on the smaller array to efficiently locate this partition.

Hard Modified Binary Search

Problem

Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays combined. The overall run time complexity should be O(log (m+n)).

nums1.length == m
nums2.length == n
0 ≤ m, n ≤ 1000
1 ≤ m + n ≤ 2000
−10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

Example

Input: nums1 = [1, 3], nums2 = [2]

Output: 2.0

The combined sorted array is [1, 2, 3]. The median is the middle element 2. The algorithm uses binary search on the smaller array to find a partition such that all elements on the left side of the partition are less than or equal to all elements on the right side. It calculates indices i and j to partition nums1 and nums2 respectively. By comparing boundary elements around the partitions, it adjusts the search space until the correct partition is found. Then, depending on the total length parity, it returns either the minimum of the right partition elements or the average of the max left and min right elements.

Approach

Straightforward Solution

A naive approach merges the two arrays and then finds the median, which takes O(m+n) time and space. This is inefficient for large inputs and does not meet the O(log(m+n)) time requirement.

Core Observation

The median splits the combined sorted array into two halves of equal length (or nearly equal if odd). The key is to find a partition between the two arrays such that all elements on the left are less than or equal to all elements on the right.

Path to Optimal

Preview

The problem's O(log(m+n)) time constraint signals a binary search approach…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use binary search on the smaller array to find the partition index i. Calculate j = half - i - 2 to partition the second array accordingly…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log(min(m, n)))

The binary search is performed on the smaller array, which has length min(m, n). Each iteration halves the search space, leading to logarithmic time complexity.

Space

O(1)

Only a fixed number of variables are used for indices and boundary values, with no additional data structures proportional to input size.

Pattern Spotlight

Modified Binary Search (Partitioning Technique)

When searching for a median or kth element across two sorted arrays, transform the problem into finding a partition point that balances elements on both sides, then use binary search on the smaller array to efficiently locate this partition.

Solution

Python

1class Solution:
  def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
      A, B = nums1, nums2
      total = len(nums1) + len(nums2)
      half = total // 2
6
      if len(B) < len(A):
          A, B = B, A
      
      l, r = 0, len(A) - 1
      while True:
          i = (l + r) // 2 
          j = half - i - 2 
14
          Aleft = A[i] if i >= 0 else float("-infinity")
          Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
          Bleft = B[j] if j >= 0 else float("-infinity")
          Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
19
          if Aleft <= Bright and Bleft <= Aright:
              if total % 2:
                  return min(Aright, Bright)
              return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
          elif Aleft > Bright:
              r = i - 1
          else:
              l = i + 1

Step-by-Step Solution

Ensure Binary Search on the Smaller Array to Minimize Search Space

3A, B = nums1, nums2
7if len(B) < len(A):
8    A, B = B, A

Objective

To guarantee the binary search is performed on the smaller array, reducing complexity and simplifying boundary conditions.

Key Insight

By swapping the arrays if the second is smaller, the algorithm ensures the binary search operates on the smaller array. This prevents out-of-bound partition indices and keeps the search space minimal, which is critical for achieving O(log(min(m,n))) time complexity.

Interview Quick-Check

Core Logic

Swapping arrays ensures the binary search is always on the smaller array, which bounds the search space and simplifies partition calculations.

Common Pitfalls & Bugs

Failing to swap can cause invalid partition indices and complicate boundary checks, leading to incorrect results or runtime errors.

Perform Binary Search to Find Correct Partition Indices

To locate partition indices i and j such that all elements on the left are less than or equal to those on the right.

Calculate and Return Median Based on Partition Validity and Total Length Parity

To compute the median once the correct partition is found, considering whether the total length is odd or even.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 20 Critical

if Aleft <= Bright and Bleft <= Aright:

Check whether the current partition is valid.

This is the core correctness test: the partition is valid only when every left-side boundary is less than or equal to the opposite right-side boundary.

Line 7 Critical

if len(B) < len(A):

Check whether the arrays should be swapped so A is the smaller array.

Binary searching the smaller array keeps the search space minimal and prevents awkward partition bounds.

Line 23 Critical

return (max(Aleft, Bleft) + min(Aright, Bright)) / 2

Return the even-length median.

For an even total length, the median is the average of the largest left-side value and the smallest right-side value.

Full line-by-line criticality + rationale for all 21 lines available on Pro.

Test Your Understanding

Why is it necessary to always binary search the smaller array instead of the larger one?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Median of Two Sorted Arrays from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Median of Two Sorted Arrays drill

or drill a free problem

1	`class Solution:`
2	`def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:`
3	`A, B = nums1, nums2`
4	`total = len(nums1) + len(nums2)`
5	`half = total // 2`
6
7	`if len(B) < len(A):`
8	`A, B = B, A`
9
10	`l, r = 0, len(A) - 1`
11	`while True:`
12	`i = (l + r) // 2`
13	`j = half - i - 2`
14
15	`Aleft = A[i] if i >= 0 else float("-infinity")`
16	`Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")`
17	`Bleft = B[j] if j >= 0 else float("-infinity")`
18	`Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")`
19
20	`if Aleft <= Bright and Bleft <= Aright:`
21	`if total % 2:`
22	`return min(Aright, Bright)`
23	`return (max(Aleft, Bleft) + min(Aright, Bright)) / 2`
24	`elif Aleft > Bright:`
25	`r = i - 1`
26	`else:`
27	`l = i + 1`