What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

8. Median of Two Sorted Arrays • Invariant Proof & Speed-Run

Theory Context•Binary Search Boundary

HardLC 4

Median of Two Sorted Arrays (LC 4)

Target Frequency:GoogleMetaAmazonAppleMicrosoft

You're given two already-sorted arrays, nums1 (size m) and nums2 (size n). Without necessarily merging them, work out the median value of all m + n numbers combined.

Target an overall running time of O(log(m + n)).

Worked Examples

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.

⚖️Formal Constraints & Bounds

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

Deep-Dive & Conceptual Insights

Core Insight

Search how many values to take from the shorter list, not a value. The left side of a cut that takes i values from one list and k - i from the other holds exactly k values. 'Is right1 at least left2?' is False and then True as i grows, so Lower Bound finds the cut. Use inf and -inf for a missing value at an edge.

Real-World Scenario & Production Applications

Merging pre-sorted result shards from two distributed database partitions to compute a percentile without materializing the full merged dataset.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: The Cut And Its Range

A cut takes i values from the shorter list and k - i values from the other list, so the left side holds exactly k values. Swap the lists so that nums1 is the shorter one. The candidates are the numbers of values taken from nums1, from max(0, k - n) to min(m, k).

Mathematical Recurrence / Code Invariant

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
lo = max(0, k - n)
hi = min(m, k) + 1

Step-by-Step Execution Trace Table

Step	Range `[lo, hi)`	`i`	`right1`	`left2`	`right1 >= left2`	Decision	New range
Setup						`nums1 = [1, 2]`, `nums2 = [3, 4]`. The total is 4, so the median needs the 2nd and the 3rd smallest values: two calls.
1	`[0, 3)` (k = 2)	1	`nums1[1] = 2`	`nums2[0] = 3`	False	`lo = mid + 1`	`[2, 3)`
2	`[2, 3)` (k = 2)	2	inf (no `nums1[2]`)	-inf (nothing taken from `nums2`)	True	`hi = mid`	`[2, 2)`
						The range is empty. The cut is 2, so `max(left1, left2) = max(2, -inf)` = 2.
3	`[1, 3)` (k = 3)	2	inf	`nums2[0] = 3`	True	`hi = mid`	`[1, 2)`
4	`[1, 2)` (k = 3)	1	`nums1[1] = 2`	`nums2[1] = 4`	False	`lo = mid + 1`	`[2, 2)`
						The range is empty. The cut is 2, so `max(left1, left2) = max(2, 3)` = 3. The median is (2 + 3) / 2 = 2.5.

At the edge of a list, the missing value is float('inf') or float('-inf'). Without it, step 2 would read nums1[2] and raise IndexError.

Worked on Paper

The Math, Step by Step

1. The cut the search looks for

Imagine all $m + n$ values merged into one sorted list. The code never merges. It takes the first $i$ values of the shorter list nums1 and the first $j = k - i$ values of the other list nums2. These $k$ values are the left side. The remaining values are the right side.

The left side holds exactly $k$ values for every $i$ , so the search only chooses $i$ , and $j$ follows from it.

The $k$ -th smallest value of both lists is the largest value on the left side, when the cut is right. The median is the $k$ -th smallest value for $k = \lfloor (m + n + 1) / 2 \rfloor$ . When $m + n$ is even, it is the mean of the $k$ -th and the $(k + 1)$ -th smallest values.

2. Checking one cut

Four values sit next to the two cuts:

Name	Value	Meaning
`left1`	`nums1[i - 1]`, or $-\infty$ when $i = 0$	the largest value of `nums1` on the left side
`right1`	`nums1[i]`, or $+\infty$ when $i = m$	the smallest value of `nums1` on the right side
`left2`	`nums2[k - i - 1]`, or $-\infty$ when $k - i = 0$	the largest value of `nums2` on the left side
`right2`	`nums2[k - i]`, or $+\infty$ when $k - i = n$	the smallest value of `nums2` on the right side

Each list is sorted, so left1 <= right1 and left2 <= right2 always hold. The cut is right when every left value is at most every right value. That needs only two cross checks: left1 <= right2 and left2 <= right1.

3. Why one question is enough

Move $i$ one step to the right. right1 can only grow, because nums1 is sorted. left2 can only shrink, because $k - i$ gets smaller. So the answer to "is right1 >= left2?" is False for small $i$ and True from some $i$ on.

The first $i$ where it is True is the right cut. The answer one step before it was False, so nums1[i - 1] < nums2[k - i], which is left1 < right2. Both cross checks hold.

So Lower Bound over $i$ , with the check right1 >= left2, finds the right cut. There is no second branch and no half.

4. The range and the sentinels

lo = max(0, k - n): when $k$ is larger than $n$ , at least $k - n$ values must come from nums1. hi = min(m, k) + 1: nums1 has $m$ values and the left side has $k$ values, so $i$ is at most $\min(m, k)$ . The + 1 makes hi one past the last candidate.

The values $-\infty$ and $+\infty$ are sentinels: stand-in values for a missing value at an edge. When $i = m$ , there is no nums1[i], and right1 is $+\infty$ . When $k - i = 0$ , no value is taken from nums2, and left2 is $-\infty$ . The last candidate always passes the check, so the search always finds a cut.

The code swaps the lists so that nums1 is the shorter list. The search then takes $O(\log \min(m, n))$ rounds.

5. Example 1 by hand

nums1 = [1,3], nums2 = [2]. The total is 3, so $k = 2$ and one call is enough. The first list is longer, so the code swaps them: nums1 = [2], nums2 = [1,3], with $m = 1$ and $n = 2$ . Then lo = max(0, 2 - 2) = 0 and hi = min(1, 2) + 1 = 2.

`lo`	`hi`	$i$	`right1`	`left2`	`right1 >= left2`	New range
0	2	1	$+\infty$ (no `nums1[1]`)	`nums2[0] = 1`	True	`hi = 1`
0	1	0	`nums1[0] = 2`	`nums2[1] = 3`	False	`lo = 1`

The range [1, 1) is empty, so the cut is $i = 1$ : one value from nums1 and one from nums2. left1 = 2 and left2 = 1, so the 2nd smallest value is $\max(2, 1) = 2$ . The code returns 2.0, the expected output 2.00000.

6. Example 2 by hand

nums1 = [1,2], nums2 = [3,4]. The total is 4, so $k = 2$ , and the median needs the 2nd and the 3rd smallest values: two calls.

For $k = 2$ : lo = max(0, 2 - 2) = 0, hi = min(2, 2) + 1 = 3.

`lo`	`hi`	$i$	`right1`	`left2`	`right1 >= left2`	New range
0	3	1	`nums1[1] = 2`	`nums2[0] = 3`	False	`lo = 2`
2	3	2	$+\infty$	$-\infty$ (nothing taken from `nums2`)	True	`hi = 2`

The cut is $i = 2$ : left1 = 2 and left2 = -inf, so the 2nd smallest value is 2.

For $k = 3$ : lo = max(0, 3 - 2) = 1, hi = min(2, 3) + 1 = 3. The search finds the cut $i = 2$ , so left1 = 2 and left2 = nums2[0] = 3, and the 3rd smallest value is 3.

The median is $(2 + 3) / 2 = 2.5$ . The code returns 2.5, the expected output 2.50000.

7. From the math to the code

Math	In `findMedianSortedArrays` and `kth_smallest_of_two`
search the shorter list	`if len(nums1) > len(nums2):` then swap
$k = \lfloor (m + n + 1) / 2 \rfloor$	`k = (total + 1) // 2`
$i$ from $\max(0, k - n)$ to $\min(m, k)$	`lo = max(0, k - n)` and `hi = min(m, k) + 1`
the question "is `right1 >= left2`?"	`def right1_at_least_left2(i)`
the sentinels	`float('-inf')` and `float('inf')`
find the first True	`i = binary_search_lower_bound(lo, hi, right1_at_least_left2)`
the $k$ -th smallest value	`return max(left1, left2)`
the median	one call for an odd total, two calls for an even total

Code Shape

Archetype Code Shape

Python

1	if len(nums1) > len(nums2):
2	nums1, nums2 = nums2, nums1
3	m, n = len(nums1), len(nums2)
4	def right1_at_least_left2(i: int) -> bool:
5	return right1 >= left2
6	lo = max(0, k - n)
7	hi = min(m, k) + 1
8	i = binary_search_lower_bound(lo, hi, right1_at_least_left2)
9	return max(left1, left2)

Conceptual Narrative

🧭 Conceptual Foundation: Searching for a Cut, Not a Value

The key idea of LC 4 is that we do not search for a value. We search for how many values to take from the shorter list. That count is a position, so Lower Bound runs over positions, not over values.

1. One cut, one forced cut

We want the $k$ -th smallest of two sorted lists. A cut takes $i$ values from the shorter list and $k - i$ values from the other list. The left side always holds exactly $k$ values. So choosing $i$ forces the other cut.

The cut is right when every left value is at most every right value. The largest left value is then the $k$ -th smallest.

2. One question

Four values sit next to the cut: left1, right1, left2 and right2. Each list is sorted, so only two pairs cross the cut. One question covers both: is right1 at least left2?

When $i$ grows, right1 only grows and left2 only shrinks. So the answers are False and then True, and Lower Bound finds the first True. This is the same shape as every other card in this pattern: a check, a range and one call.

3. The edges

At the edge of a list, one value is missing. When $i = m$ , there is no nums1[i]. When $k - i = 0$ , no value is taken from nums2. We write float('inf') and float('-inf') for the missing values. The trap is to read the missing value anyway: Python raises IndexError.

4. From k to the median

For an odd total, the median is the $k$ -th smallest for $k = (total + 1) // 2$ . For an even total, it is the mean of the $k$ -th and the $(k + 1)$ -th smallest values, so the code calls the helper twice.

Next step: for three or more sorted lists, or a sorted matrix, one cut no longer decides the others. Those problems use the Kth Smallest card, which searches the values and counts.

Reading past the end of a list without float('inf')
Starting lo at 0 instead of max(0, k - n)
Reading nums2[k - i] instead of nums2[k - i - 1]
Making one call when the total is even
Averaging with // instead of /

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Two sorted lists, and the median or a k-th value in less than linear time. A merge would read every value. The answer is a count of values to take from one list, so Lower Bound runs over counts.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: a cut that takes i values from the shorter list and k - i values from the other puts exactly k values on the left. Every cut before lo has right1 smaller than left2, and the cut at hi passes. The check right1 >= left2 is False and then True as i grows.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Reading past the end of a list: when i == m there is no nums1[i], and when k - i == 0 no value is taken from nums2. Without float('inf') and float('-inf'), kth_smallest_of_two([1, 3], [2, 4], 4) raises IndexError.
Starting lo at 0: when k is larger than n, i = 0 makes k - i larger than n, and nums2[k - i - 1] is past the end. Start at max(0, k - n).
Making one call for an even total: [1, 2] and [3, 4] need the 2nd and the 3rd smallest values. One call gives 2.0, and the median is 2.5.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"This is a Lower Bound search over a count. A cut takes i values from the shorter list and k - i from the other, so the left side holds exactly k values. I ask one question for each i: is right1 at least left2? right1 only grows and left2 only shrinks as i grows, so the answers are False and then True, and Lower Bound finds the first True. The range is max(0, k - n) to min(m, k) + 1. The largest left value is the k-th smallest. For an odd total I make one call, and for an even total I make two calls and take the mean. The trap is reading past the end of a list: I use inf and -inf for a missing value. That is O(log min(M, N)) time and O(1) space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log(min(M, N)))

Look at the structure: Lower Bound runs while lo < hi: over the cuts [max(0, k - n), min(m, k) + 1) of the shorter list, at most min(M, N) + 1 candidates. Each pass halves the range. Each pass calls right1_at_least_left2(mid), which reads two values. The median makes at most two calls. So the time is O(log min(M, N)).

SPACE COMPLEXITY

O(1)

Look at the memory used: Lower Bound and the check are iterative, so the call stack holds a few frames. Only a few integers and four boundary values exist at once. No merged list is built. Auxiliary space is O(1).

Formal Recurrence Relation

$T(M, N) = O(\log(\min(M, N)))$

Derivation Progression

Shorter-Array Restriction

search space = [0, min(M, N)]

Binary searching the shorter array bounds the search range to min(M, N) + 1 candidates.

Forced Partition

j = half - i

The partition index in the longer array is derived arithmetically, not searched, costing O(1) per iteration.

Convergence

⌊ log2(min(M, N) + 1) ⌋ + 1 iterations

Each iteration halves the min(M, N) + 1 candidate cuts, so the loop finds the correct cut within at most ⌊ log2(min(M, N) + 1) ⌋ + 1 iterations.

Variable Definitions

$M$

Length of the first sorted array

$N$

Length of the second sorted array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative while loop with zero recursion frames

🔵 Auxiliary Heap

O(1) Only scalar boundary values in CPU registers

🟢 Output Space

O(1) Returns a single floating-point median

Boundary Best / Worst Cases

Best Case

$O(1)$ when one array is empty and the other's length determines the median directly.

Average Case

$O(\log(\min(M, N)))$ .

Worst Case

$O(\log(\min(M, N)))$ for two comparably-sized arrays.

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

The statement gives "two already-sorted arrays" and asks us to "work out the median" in O(log(m + n)) time. That bound is the giveaway: we cannot merge the arrays ( $O(M + N)$ ). The answer is a count of values to take from the shorter array, so Lower Bound runs over counts: $O(\log(\min(M, N)))$ , better than asked.

CONSTRAINTS & BOUNDS

Array sizes are $M \le 1000, N \le 1000$ , and the cost depends only on the shorter array: nums1 has $M + 1$ cuts, so the search runs at most $\lfloor \log_2(M + 1) \rfloor + 1$ passes, 10 at LeetCode's limit, however long nums2 is. The range of cuts is [max(0, k - n), min(m, k) + 1).

FAANG PRODUCTION TRAPS & EDGE CASES

The card's traps are reading past the end of a list (use float('inf') and float('-inf')), starting lo at 0, and making one call for an even total. At scale there is one more: in a language with fixed-width integers, lower_middle + upper_middle can overflow before it is halved when the values are near the type's limit; halve in floating point or compute lower_middle + (upper_middle - lower_middle) / 2.

Theory Context•Binary Search Boundary

HardLC 4

Median of Two Sorted Arrays (LC 4)

Target Frequency:GoogleMetaAmazonAppleMicrosoft

You're given two already-sorted arrays, nums1 (size m) and nums2 (size n). Without necessarily merging them, work out the median value of all m + n numbers combined.

Target an overall running time of O(log(m + n)).

Worked Examples

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.

⚖️Formal Constraints & Bounds

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

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Merging pre-sorted result shards from two distributed database partitions to compute a percentile without materializing the full merged dataset.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: The Cut And Its Range

Mathematical Recurrence / Code Invariant

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
lo = max(0, k - n)
hi = min(m, k) + 1

Step-by-Step Execution Trace Table

Step	Range `[lo, hi)`	`i`	`right1`	`left2`	`right1 >= left2`	Decision	New range
Setup						`nums1 = [1, 2]`, `nums2 = [3, 4]`. The total is 4, so the median needs the 2nd and the 3rd smallest values: two calls.
1	`[0, 3)` (k = 2)	1	`nums1[1] = 2`	`nums2[0] = 3`	False	`lo = mid + 1`	`[2, 3)`
2	`[2, 3)` (k = 2)	2	inf (no `nums1[2]`)	-inf (nothing taken from `nums2`)	True	`hi = mid`	`[2, 2)`
						The range is empty. The cut is 2, so `max(left1, left2) = max(2, -inf)` = 2.
3	`[1, 3)` (k = 3)	2	inf	`nums2[0] = 3`	True	`hi = mid`	`[1, 2)`
4	`[1, 2)` (k = 3)	1	`nums1[1] = 2`	`nums2[1] = 4`	False	`lo = mid + 1`	`[2, 2)`
						The range is empty. The cut is 2, so `max(left1, left2) = max(2, 3)` = 3. The median is (2 + 3) / 2 = 2.5.

At the edge of a list, the missing value is float('inf') or float('-inf'). Without it, step 2 would read nums1[2] and raise IndexError.

Worked on Paper

The Math, Step by Step

1. The cut the search looks for

The left side holds exactly $k$ values for every $i$ , so the search only chooses $i$ , and $j$ follows from it.

2. Checking one cut

Four values sit next to the two cuts:

Name	Value	Meaning
`left1`	`nums1[i - 1]`, or $-\infty$ when $i = 0$	the largest value of `nums1` on the left side
`right1`	`nums1[i]`, or $+\infty$ when $i = m$	the smallest value of `nums1` on the right side
`left2`	`nums2[k - i - 1]`, or $-\infty$ when $k - i = 0$	the largest value of `nums2` on the left side
`right2`	`nums2[k - i]`, or $+\infty$ when $k - i = n$	the smallest value of `nums2` on the right side

3. Why one question is enough

The first $i$ where it is True is the right cut. The answer one step before it was False, so nums1[i - 1] < nums2[k - i], which is left1 < right2. Both cross checks hold.

So Lower Bound over $i$ , with the check right1 >= left2, finds the right cut. There is no second branch and no half.

4. The range and the sentinels

The code swaps the lists so that nums1 is the shorter list. The search then takes $O(\log \min(m, n))$ rounds.

5. Example 1 by hand

`lo`	`hi`	$i$	`right1`	`left2`	`right1 >= left2`	New range
0	2	1	$+\infty$ (no `nums1[1]`)	`nums2[0] = 1`	True	`hi = 1`
0	1	0	`nums1[0] = 2`	`nums2[1] = 3`	False	`lo = 1`

6. Example 2 by hand

nums1 = [1,2], nums2 = [3,4]. The total is 4, so $k = 2$ , and the median needs the 2nd and the 3rd smallest values: two calls.

For $k = 2$ : lo = max(0, 2 - 2) = 0, hi = min(2, 2) + 1 = 3.

`lo`	`hi`	$i$	`right1`	`left2`	`right1 >= left2`	New range
0	3	1	`nums1[1] = 2`	`nums2[0] = 3`	False	`lo = 2`
2	3	2	$+\infty$	$-\infty$ (nothing taken from `nums2`)	True	`hi = 2`

The cut is $i = 2$ : left1 = 2 and left2 = -inf, so the 2nd smallest value is 2.

For $k = 3$ : lo = max(0, 3 - 2) = 1, hi = min(2, 3) + 1 = 3. The search finds the cut $i = 2$ , so left1 = 2 and left2 = nums2[0] = 3, and the 3rd smallest value is 3.

The median is $(2 + 3) / 2 = 2.5$ . The code returns 2.5, the expected output 2.50000.

7. From the math to the code

Math	In `findMedianSortedArrays` and `kth_smallest_of_two`
search the shorter list	`if len(nums1) > len(nums2):` then swap
$k = \lfloor (m + n + 1) / 2 \rfloor$	`k = (total + 1) // 2`
$i$ from $\max(0, k - n)$ to $\min(m, k)$	`lo = max(0, k - n)` and `hi = min(m, k) + 1`
the question "is `right1 >= left2`?"	`def right1_at_least_left2(i)`
the sentinels	`float('-inf')` and `float('inf')`
find the first True	`i = binary_search_lower_bound(lo, hi, right1_at_least_left2)`
the $k$ -th smallest value	`return max(left1, left2)`
the median	one call for an odd total, two calls for an even total

Code Shape

Archetype Code Shape

Python

1	if len(nums1) > len(nums2):
2	nums1, nums2 = nums2, nums1
3	m, n = len(nums1), len(nums2)
4	def right1_at_least_left2(i: int) -> bool:
5	return right1 >= left2
6	lo = max(0, k - n)
7	hi = min(m, k) + 1
8	i = binary_search_lower_bound(lo, hi, right1_at_least_left2)
9	return max(left1, left2)

Conceptual Narrative

🧭 Conceptual Foundation: Searching for a Cut, Not a Value

1. One cut, one forced cut

The cut is right when every left value is at most every right value. The largest left value is then the $k$ -th smallest.

2. One question

Four values sit next to the cut: left1, right1, left2 and right2. Each list is sorted, so only two pairs cross the cut. One question covers both: is right1 at least left2?

3. The edges

4. From k to the median

Next step: for three or more sorted lists, or a sorted matrix, one cut no longer decides the others. Those problems use the Kth Smallest card, which searches the values and counts.

Reading past the end of a list without float('inf')
Starting lo at 0 instead of max(0, k - n)
Reading nums2[k - i] instead of nums2[k - i - 1]
Making one call when the total is even
Averaging with // instead of /

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Two sorted lists, and the median or a k-th value in less than linear time. A merge would read every value. The answer is a count of values to take from one list, so Lower Bound runs over counts.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Reading past the end of a list: when i == m there is no nums1[i], and when k - i == 0 no value is taken from nums2. Without float('inf') and float('-inf'), kth_smallest_of_two([1, 3], [2, 4], 4) raises IndexError.
Starting lo at 0: when k is larger than n, i = 0 makes k - i larger than n, and nums2[k - i - 1] is past the end. Start at max(0, k - n).
Making one call for an even total: [1, 2] and [3, 4] need the 2nd and the 3rd smallest values. One call gives 2.0, and the median is 2.5.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"This is a Lower Bound search over a count. A cut takes i values from the shorter list and k - i from the other, so the left side holds exactly k values. I ask one question for each i: is right1 at least left2? right1 only grows and left2 only shrinks as i grows, so the answers are False and then True, and Lower Bound finds the first True. The range is max(0, k - n) to min(m, k) + 1. The largest left value is the k-th smallest. For an odd total I make one call, and for an even total I make two calls and take the mean. The trap is reading past the end of a list: I use inf and -inf for a missing value. That is O(log min(M, N)) time and O(1) space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log(min(M, N)))

SPACE COMPLEXITY

O(1)

Formal Recurrence Relation

$T(M, N) = O(\log(\min(M, N)))$

Derivation Progression

Shorter-Array Restriction

search space = [0, min(M, N)]

Binary searching the shorter array bounds the search range to min(M, N) + 1 candidates.

Forced Partition

j = half - i

The partition index in the longer array is derived arithmetically, not searched, costing O(1) per iteration.

Convergence

⌊ log2(min(M, N) + 1) ⌋ + 1 iterations

Each iteration halves the min(M, N) + 1 candidate cuts, so the loop finds the correct cut within at most ⌊ log2(min(M, N) + 1) ⌋ + 1 iterations.

Variable Definitions

$M$

Length of the first sorted array

$N$

Length of the second sorted array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative while loop with zero recursion frames

🔵 Auxiliary Heap

O(1) Only scalar boundary values in CPU registers

🟢 Output Space

O(1) Returns a single floating-point median

Boundary Best / Worst Cases

Best Case

$O(1)$ when one array is empty and the other's length determines the median directly.

Average Case

$O(\log(\min(M, N)))$ .

Worst Case

$O(\log(\min(M, N)))$ for two comparably-sized arrays.

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Step

Range [lo, hi)

i

right1

left2

right1 >= left2

Decision

New range

Setup

nums1 = [1, 2], nums2 = [3, 4]. The total is 4, so the median needs the 2nd and the 3rd smallest values: two calls.

[0, 3) (k = 2)

nums1[1] = 2

nums2[0] = 3

False

lo = mid + 1

[2, 3)

[2, 3) (k = 2)

inf (no nums1[2])

-inf (nothing taken from nums2)

True

hi = mid

[2, 2)

The range is empty. The cut is 2, so max(left1, left2) = max(2, -inf) = 2.

[1, 3) (k = 3)

inf

nums2[0] = 3

True

hi = mid

[1, 2)

[1, 2) (k = 3)

nums1[1] = 2

nums2[1] = 4

False

lo = mid + 1

[2, 2)

The range is empty. The cut is 2, so max(left1, left2) = max(2, 3) = 3. The median is (2 + 3) / 2 = 2.5.

Name

Value

Meaning

left1

nums1[i - 1], or

-\infty

when

i = 0

the largest value of nums1 on the left side

right1

nums1[i], or

+\infty

when

i = m

the smallest value of nums1 on the right side

left2

nums2[k - i - 1], or

-\infty

when

k - i = 0

the largest value of nums2 on the left side

right2

nums2[k - i], or

+\infty

when

k - i = n

the smallest value of nums2 on the right side

lo

hi

i

right1

left2

right1 >= left2

New range

+\infty

(no nums1[1])

nums2[0] = 1

True

hi = 1

nums1[0] = 2

nums2[1] = 3

False

lo = 1

lo

hi

i

right1

left2

right1 >= left2

New range

nums1[1] = 2

nums2[0] = 3

False

lo = 2

+\infty

-\infty

(nothing taken from nums2)

True

hi = 2

Math

In findMedianSortedArrays and kth_smallest_of_two

search the shorter list

if len(nums1) > len(nums2): then swap

k = \lfloor (m + n + 1) / 2 \rfloor

k = (total + 1) // 2

i

from

\max(0, k - n)

\min(m, k)

lo = max(0, k - n) and hi = min(m, k) + 1

the question "is right1 >= left2?"

def right1_at_least_left2(i)

the sentinels

float('-inf') and float('inf')

find the first True

i = binary_search_lower_bound(lo, hi, right1_at_least_left2)

the

k

-th smallest value

return max(left1, left2)

the median

one call for an odd total, two calls for an even total

Step

Range [lo, hi)

i

right1

left2

right1 >= left2

Decision

New range

Setup

nums1 = [1, 2], nums2 = [3, 4]. The total is 4, so the median needs the 2nd and the 3rd smallest values: two calls.

[0, 3) (k = 2)

nums1[1] = 2

nums2[0] = 3

False

lo = mid + 1

[2, 3)

[2, 3) (k = 2)

inf (no nums1[2])

-inf (nothing taken from nums2)

True

hi = mid

[2, 2)

The range is empty. The cut is 2, so max(left1, left2) = max(2, -inf) = 2.

[1, 3) (k = 3)

inf

nums2[0] = 3

True

hi = mid

[1, 2)

[1, 2) (k = 3)

nums1[1] = 2

nums2[1] = 4

False

lo = mid + 1

[2, 2)

The range is empty. The cut is 2, so max(left1, left2) = max(2, 3) = 3. The median is (2 + 3) / 2 = 2.5.

Name

Value

Meaning

left1

nums1[i - 1], or

-\infty

when

i = 0

the largest value of nums1 on the left side

right1

nums1[i], or

+\infty

when

i = m

the smallest value of nums1 on the right side

left2

nums2[k - i - 1], or

-\infty

when

k - i = 0

the largest value of nums2 on the left side

right2

nums2[k - i], or

+\infty

when

k - i = n

the smallest value of nums2 on the right side

lo

hi

i

right1

left2

right1 >= left2

New range

+\infty

(no nums1[1])

nums2[0] = 1

True

hi = 1

nums1[0] = 2

nums2[1] = 3

False

lo = 1

lo

hi

i

right1

left2

right1 >= left2

New range

nums1[1] = 2

nums2[0] = 3

False

lo = 2

+\infty

-\infty

(nothing taken from nums2)

True

hi = 2

Math

In findMedianSortedArrays and kth_smallest_of_two

search the shorter list

if len(nums1) > len(nums2): then swap

k = \lfloor (m + n + 1) / 2 \rfloor

k = (total + 1) // 2

i

from

\max(0, k - n)

\min(m, k)

lo = max(0, k - n) and hi = min(m, k) + 1

the question "is right1 >= left2?"

def right1_at_least_left2(i)

the sentinels

float('-inf') and float('inf')

find the first True

i = binary_search_lower_bound(lo, hi, right1_at_least_left2)

the

k

-th smallest value

return max(left1, left2)

the median

one call for an odd total, two calls for an even total

🧭 Conceptual Foundation: Searching for a Cut, Not a Value

1. One cut, one forced cut

The cut is right when every left value is at most every right value. The largest left value is then the $k$ -th smallest.

2. One question

Four values sit next to the cut: left1, right1, left2 and right2. Each list is sorted, so only two pairs cross the cut. One question covers both: is right1 at least left2?

3. The edges

4. From k to the median

Next step: for three or more sorted lists, or a sorted matrix, one cut no longer decides the others. Those problems use the Kth Smallest card, which searches the values and counts.