← all entries
A-034● Day 342026.06.09hardleetcode #4neetcode150

Median of Two Sorted Arrays

#array#binary-search#divide-and-conquer
↗ leetcode #4 · median-of-two-sorted-arrays
01

Problem

· problem
P.034

Median of Two Sorted Arrays

↗ leetcode #4

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

constraints
  • · 0 ≤ m ≤ 1000, 0 ≤ n ≤ 1000
  • · 1 ≤ m + n ≤ 2000
  • · -10^6 ≤ nums1[i], nums2[i] ≤ 10^6
// paraphrased summary — see source for full text
examples
example 1input → output
[1,3]
[2]
2.00000
example 2input → output
[1,2]
[3,4]
2.50000
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What exactly is the median?
  • ☐
    Can one or both arrays be empty?
  • ☐
    Why must the time complexity be O(log(m+n))?
  • ☐
    Can the arrays contain negative numbers?
  • ☐
    Can there be duplicate values?
  • ☐
    Is the median always an integer?
  • ☐
    Must we use the arrays in their original order?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Calculate total length and target position
○
total = len(nums1) + len(nums2)
○
total = len(nums1) + len(nums2) + 1
○
total = max(len(nums1), len(nums2))
step 2· Ensure A is the smaller array
○
if len(B) < len(A):
○
if len(A) < len(B): A, B = B, A
○
A, B = B, A
step 3· Initialize binary search bounds
○
l, r = 0, len(A) - 1
○
l, r = 0, len(B) - 1
○
l, r = 0, half
step 4· Calculate partition index in B│ nested
○
j = half - i - 2  # B
○
j = half - i - 1
○
j = half - i
step 5· Extract boundary values at partition│ nested
○
Aleft = A[i] if i >= 0 else float("-infinity")
○
Aleft = A[i] if i >= 0 else float('infinity')
○
Aleft = A[i - 1] if i > 0 else float('-infinity')
step 6· Validate partition correctness│ nested
○
if Aleft <= Bright and Bleft <= Aright:
○
if Aleft <= Bright or Bleft <= Aright:
○
if Aleft < Bright and Bleft < Aright:
step 7· Adjust binary search range│ nested
○
elif Aleft > Bright:
○
elif Aleft < Bright: r = i - 1
○
elif Aleft > Bright: l = i + 1
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Time: log(min(n, m))
2
3
4
class Solution:
5
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
6
        A, B = nums1, nums2
7
        total = len(nums1) + len(nums2)
8
        half = total // 2
9
10
        if len(B) < len(A):
11
            A, B = B, A
12
13
        l, r = 0, len(A) - 1
14
        while True:
15
            i = (l + r) // 2  # A
16
            j = half - i - 2  # B
17
18
            Aleft = A[i] if i >= 0 else float("-infinity")
19
            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
20
            Bleft = B[j] if j >= 0 else float("-infinity")
21
            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
22
23
            # partition is correct
24
            if Aleft <= Bright and Bleft <= Aright:
25
                # odd
26
                if total % 2:
27
                    return min(Aright, Bright)
28
                # even
29
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
30
            elif Aleft > Bright:
31
                r = i - 1
32
            else:
33
                l = i + 1
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,3]
[2]
→
2.00000
case 2
[1,2]
[3,4]
→
2.50000
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.