Median of Two Sorted Arrays — LeetCode Daily Python Solution (the trick nobody sees)

Introduction

Median of Two Sorted Arrays has a reputation. It's one of the few problems LeetCode tags as "Hard" that also shows up constantly in interviews at large tech companies, and the reason isn't that the code is long — the final solution is barely twenty lines. The reason is that almost everyone's first instinct is wrong for the constraints being asked.

Most people can solve this problem in O(m + n) time in under a minute: merge the arrays, find the middle. The interviewer already expects that. What they're testing is whether you can recognize that merging is unnecessary — that you can reason about the position of the median without ever touching most of the data. That skill, binary searching over an abstract "answer space" instead of a concrete array index, is one of the most reusable patterns in algorithm interviews. It reappears in problems about kth-smallest elements across multiple lists, capacity-to-ship-in-days problems, and split-array-largest-sum problems. Learning it once here pays off many times later.

Problem Overview

You're given two arrays, nums1 and nums2, and both are already sorted in ascending order. Your job is to find the median of the combined set of all their elements — as if you had merged both arrays into one sorted array and then picked the middle value (or averaged the two middle values, if the total count is even).

The twist that makes this "Hard" is the required time complexity: O(log(min(m, n))), where m and n are the lengths of the two arrays. That rules out actually merging the arrays, and it even rules out a straightforward O(m + n) single pass. You need an approach whose running time barely grows even as the arrays get enormous — and that's a strong signal the problem wants binary search.

Example

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

Merged conceptually: [1, 2, 3]. Three elements total, so the median is the single middle value: 2.

A second example with an even total:

nums1 = [1, 2]
nums2 = [3, 4]

Merged conceptually: [1, 2, 3, 4]. Four elements, so the median is the average of the two middle values, 2 and 3: 2.5.

Notice both arrays stay untouched in memory in the real solution — these merged lists are just how we're reasoning about the expected answer, not something the algorithm actually builds.

Intuition

Here's how an engineer who's seen binary-search-on-answer problems before would approach this.

The brute-force instinct is to physically build the merged array and index into the middle. That's correct, but it processes every element — O(m + n) — and the problem is explicitly asking for something logarithmic. Logarithmic time is a strong hint: it usually means "you can throw away half of your remaining search space at each step," which is the definition of binary search. But binary search over what? There's no single sorted array to search over.

The insight is that instead of searching for a value, you can search for a position — specifically, a way to slice both arrays simultaneously so that everything to the left of both cuts, combined, is exactly the left half of the total elements, and everything to the right is the right half.

Picture both arrays as two rows of cards. You slide one divider through each row at the same time. If you can find dividers such that:

• every card left of either divider is ≤ every card right of either divider

...then you've found the correct partition, and the median sits right at that boundary — no merging needed. You only ever need to look at four cards: the one just left and just right of each divider.

Since a valid divider position in nums1 fully determines the required divider position in nums2 (the two must add up to exactly half the total count), you only need to binary search one array — and to keep the search space as small as possible, you always binary search the shorter array. That's where O(log(min(m, n))) comes from.

Brute Force Solution

Idea: Merge both arrays into one sorted array, then index into the middle.

Algorithm:

1. Merge nums1 and nums2 using a standard two-pointer merge (like the merge step of merge sort).
2. If the total length is odd, return the single middle element.
3. If even, return the average of the two middle elements.

Advantages: Trivial to write and reason about; easy to verify by hand.

Disadvantages: Touches every element, and allocates extra memory for the merged array — both violate the problem's required complexity.

Complexity: Time O(m + n), Space O(m + n).

Optimal Solution

We binary search over how many elements of the shorter array (call it nums1, after swapping if needed) go into the left half of the final merged sequence. Call that count i. Because the left half must always contain exactly half = (m + n + 1) // 2 elements total, the matching count from nums2 is forced: j = half - i.

At any guess i, we look at four border values:

Name	Meaning	Value if out of bounds
left1	last element in nums1's left partition	-infinity if i == 0
right1	first element in nums1's right partition	+infinity if i == m
left2	last element in nums2's left partition	-infinity if j == 0
right2	first element in nums2's right partition	+infinity if j == n

The partition is correct when left1 <= right2 and left2 <= right1. If left1 > right2, we included too many elements from nums1 on the left, so we move the guess i down. Otherwise, we move it up. This is standard binary search, just applied to a partition count instead of an array index.

Once the correct partition is found:

• If the total length is odd, the median is max(left1, left2).
• If even, the median is the average of max(left1, left2) and min(right1, right2).

The (m + n + 1) // 2 formula (note the +1) is what makes both the odd and even cases fall out of the same code path without a separate branch — for odd totals, the left half simply ends up one element larger, which is exactly the extra element the odd-case return picks up.

Python Code

from typing import List


def find_median_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
    # Always binary search the shorter array to minimize the search space.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2
    lo, hi = 0, m

    while lo <= hi:
        i = (lo + hi) // 2       # partition index in nums1
        j = half - i             # forced partition index in nums2

        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")

        if left1 <= right2 and left2 <= right1:
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            hi = i - 1
        else:
            lo = i + 1

    raise ValueError("Input arrays must be sorted")

Code Walkthrough

• Swap step: guarantees nums1 is the shorter (or equal-length) array, which is what keeps j guaranteed to land inside [0, n] for every i we try.
• half: the required size of the combined left half, computed once outside the loop.
• lo, hi = 0, m: the binary search range is over how many elements of nums1 to place on the left — not over values, and not over nums1's indices in the usual sense.
• i and j: i is our guess; j is derived, not guessed, since the two must always sum to half.
• Sentinel infinities: let a partition sit exactly at an array's start or end without special-casing — there's simply "nothing" on that side, and infinity/negative-infinity behave correctly in comparisons.
• The condition: left1 <= right2 and left2 <= right1 is the correctness check. Note the code never explicitly checks the reverse direction as a third branch — if left1 > right2 fails, left2 > right1 is the only remaining failure mode, so the else covers it.
• Median extraction: odd totals take the max of both left values; even totals average that max with the min of both right values.

Dry Run

nums1 = [1, 3], nums2 = [2]. Already nums1 is the shorter array, so no swap. m = 2, n = 1, half = (2 + 1 + 1) // 2 = 2.

lo = 0, hi = 2. First guess: i = 1, so j = half - i = 1.

• left1 = nums1[0] = 1
• right1 = nums1[1] = 3
• left2 = nums2[0] = 2
• right2 = +inf (j == n, nothing left in nums2)

Check: left1 (1) <= right2 (inf) ✓, left2 (2) <= right1 (3) ✓. Partition is valid.

Total length m + n = 3 is odd, so return max(left1, left2) = max(1, 2) = 2.

Matches the expected answer from merging by hand: [1, 2, 3] → median 2.

Complexity Analysis

Time: O(log(min(m, n))) — the binary search only ever runs over the shorter array's index range, halving the range each iteration; j is computed in O(1), not searched.

Space: O(1) — no merged array, no auxiliary data structures; only a handful of scalar variables.

Why these are correct: because both arrays are individually sorted, moving i monotonically moves left1/right1 monotonically as well. That monotonicity is exactly what guarantees binary search converges to the correct partition rather than getting stuck or oscillating.

Alternative Solutions

A reasonable middle ground between brute force and the optimal partition trick is a two-pointer "count to the middle" walk: advance pointers through both arrays simultaneously, counting elements, and stop once you've passed the halfway point, tracking the last one or two values seen. This avoids allocating a merged array (O(1) space) but still runs in O(m + n) time, since it walks roughly half of the combined elements. It's a fine fallback if you're asked to solve this without hitting logarithmic time, and it's a good way to sanity-check the partition solution against a smaller, easier-to-trust approach.

Edge Cases

• One array is empty: the sentinel infinities take over — the divider index for the empty array pins to 0 for its entire binary search, and the logic still holds.
• Arrays of very different lengths: handled automatically, since we always binary search the shorter array regardless of how large the other one is.
• Duplicate values across both arrays: the <= comparison (not strict <) correctly allows ties at the cut boundary.
• Single-element arrays: works the same way — i and j can only be 0 or 1, and the sentinels handle both boundary positions.
• Total length is even vs. odd: both handled by the same (m + n + 1) // 2 formula without a separate code path for each case.

Common Mistakes

1. Binary searching the longer array instead of the shorter one. This can push j outside a valid range and requires extra bounds handling that the shorter-array approach avoids entirely.
2. Forgetting the sentinel infinities, causing index-out-of-range errors when a partition sits at an array's edge.
3. Using strict < instead of <= in the validity check, which incorrectly rejects valid partitions when duplicate values sit right at the cut.
4. Miscomputing half — dropping the +1 breaks the odd-length case, since the left half needs to be one element larger for odd totals.
5. Actually merging the arrays to "double check," then submitting that as the final solution — it passes small test cases but fails the time complexity requirement on large inputs.

Interview Questions

• "Can you do better than O(log(min(m, n)))?" — No, for arbitrary sorted arrays, you need at least that many comparisons to locate the correct partition boundary in the worst case.
• "What if nums2 were empty?" — j pins to 0 for the entire search, and the sentinel infinities on nums2's side handle it without any special-casing.
• "How would you find the kth smallest element across two sorted arrays instead of the median?" — Same invariant, different target size for the left half.
• "Why do we always search the smaller array?" — Because the partition point in the larger array is derived from it; searching the larger array wastes steps and risks an invalid j.

Similar Problems

• Kth Smallest Element in Two Sorted Arrays — the exact same partition invariant, generalized to an arbitrary target rank instead of the median.
• Merge Sorted Array (LeetCode 88) — the brute-force building block this problem asks you to avoid; useful for understanding why merging is O(m + n).
• Capacity To Ship Packages Within D Days — another "binary search on the answer" problem, where you search a value range instead of an array index.
• Split Array Largest Sum — same underlying pattern: binary search over a monotonic predicate rather than concrete indices.

Key Takeaways

Merging is the obvious first move, but it's the wrong tool once a problem explicitly asks for logarithmic time. The real lesson here is recognizing when you can binary search over an abstract quantity — a partition count, a capacity, a target sum — rather than over a literal array index. Once you spot that pattern, this "Hard" problem collapses into checking four numbers and nudging a guess left or right.

Watch the Video

For the full visual walkthrough — including the card-and-divider mental model and a live trace of the binary search — check out the video here: {LINK}

About the Series

This breakdown is part of the Daily Python LeetCode series, where one problem gets solved from first principles every day — brute force first, then the optimal approach, with full Python code and a dry run every time. The goal is to build real intuition, not just memorize solutions.

Call To Action

If this helped the partition trick click, drop a like on the video — it's the simplest way to tell me it landed. Subscribe on YouTube for tomorrow's problem, and subscribe to the Substack if you'd rather get the full write-up in your inbox. Comments with your own dry runs or alternative approaches are always welcome, and sharing this with someone prepping for interviews helps more than you'd think.

---

    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        left1 = nums1[i-1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j-1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')