Skip to content

Volume ITechnology

4.11.7 — Median of Two Sorted Arrays ​

LeetCode 4 · Hard

The problem ​

Two sorted arrays. Find the median of their combined contents, in O(\log(m+n)).

nums1 = [1,3], nums2 = [2]        →  2.0      (merged: [1,2,3])
nums1 = [1,2], nums2 = [3,4]      →  2.5      (merged: [1,2,3,4])

To put this in plain English: you are given two arrays that are individually sorted. If you were to combine them into one massive sorted array, what would be the number in the exact middle? If the combined size is even, take the average of the two middle numbers.

Constraints to Keep in Mind: ​

  • nums1.length == m, nums2.length == n
  • 0 <= m <= 1000, 0 <= n <= 1000
  • 1 <= m + n <= 2000 (Both won't be empty at the same time)
  • -10^6 <= nums1[i], nums2[i] <= 10^6

The brute force, and where it wastes work ​

The simplest idea is just to merge the two arrays.

  • How it works: You can create a new array merged and use two pointers (like in Merge Sort) to combine nums1 and nums2 into a single sorted list. Then, depending on whether the total length is odd or even, you return the middle element or the average of the two middle elements.
  • Why it's too slow: Creating and filling a new array takes O(m + n) time and O(m + n) extra space. Alternatively, you could just keep track of the middle elements without storing the full merged array, reducing space to O(1), but the time is still O(m + n). The problem explicitly rules this out and demands O(\log(m+n)), meaning we must use binary search.

The pattern ​

The median splits the combined data into two halves of equal size, where everything in the left half is at most everything in the right half. So instead of finding a value, find the cut.

Draw a vertical line through both arrays at once:

A:  a0  a1  a2 | a3  a4
B:  b0  b1     | b2  b3  b4
    └── left ──┘└── right ──┘

Take i elements from the front of A and j from the front of B. If you want a total of half elements on the left, then j is forced:

j = \text{half} - i

That is the first key idea. You only choose i. The value of j follows, so there is one dimension to search, not two.

The second key idea is the condition for a correct cut. Everything on the left must be at most everything on the right. Within each array that is automatic, since both are sorted. What has to be checked is the two cross comparisons:

A_{\text{left}} \le B_{\text{right}} \quad\text{and}\quad B_{\text{left}} \le A_{\text{right}}

where A_left is the last element taken from A, A_right the first element left behind, and likewise for B.

If both hold, the cut is correct and the median is right there at the boundary. If A_left > B_right, you took too much from A, so move the cut left. If B_left > A_right, you took too little, so move right.

That is a monotonic condition, so binary search i.

Three details that make it work ​

Binary search the shorter array. Then j = half - i can never fall outside B's bounds. Search the longer one and j can go negative or past the end, and you spend the rest of your life adding guards.

Use the fence model. The cut can be anywhere from "take nothing from A" to "take all of A", which is len(A) + 1 positions for an array of length len(A). So low = 0 and high = len(A), one past the last index. This is the fence model from 4.11.1: you are choosing a gap between elements, not an element.

Picture a fence between posts. The elements are post slots; the fence is what goes between them. An array of length 5 has six places to put a fence — before the first element, between each pair, or after the last:

  fence positions:   0    1    2    3    4    5
                     |    |    |    |    |    |
  array slots:     [ a0 , a1 , a2 , a3 , a4 ]
                     |    |    |    |    |    |
                  fence  fence  ...            fence
                  here   here                  here

When you set i = 2, you are dropping the fence at position 2. That means two elements go to the left (a0, a1) and the rest go to the right (a2, a3, a4). No element is "the fence" — the fence lives in the gap between a1 and a2.

Now here is the part that trips people up: what does i actually point at in array-index terms?

  • i is the starting index of the right side. When the fence is at position 2, the right side starts at A[2], which is a2. So A_right = A[i].
  • i - 1 is the last index of the left side. The left side ends at A[1], which is a1. So A_left = A[i - 1].

Think of i as answering the question "how many elements did I take?" If you took 2, then indices 0 and 1 are on the left (that's i - 1 = 1 at the boundary) and index 2 onward is on the right (that's i = 2 at the boundary). The fence sits in the gap between index i - 1 and index i.

The edge cases follow naturally. i = 0 means "take nothing from A" — there is no A[i - 1], so A_left is -\infty. i = len(A) means "take everything from A" — there is no A[i], so A_right is +\infty.

The same logic applies to B with j: B_left = B[j - 1] and B_right = B[j].

Use infinities at the edges. If i == 0 nothing was taken from A, so A_left should never block the comparison — set it to -\infty. If i == len(A) nothing is left behind, so A_right is +\infty. This removes every boundary branch, and it is the trick that turns a mess of if statements into four clean lines.

Getting the halves right ​

Let total = m + n and half = (total + 1) // 2.

The + 1 rounds up, which means that when the total is odd, the left side gets the extra element and the median is the largest value on the left. When the total is even, the two sides are equal and the median is the average of the largest on the left and the smallest on the right.

Doing it this way means one formula covers both cases with a single if at the end.

Why the median always lands on the left for odd totals ​

This is the part that feels wrong until you see it on paper. You might think: "i is the first index of the right side, so isn't the median on the right?" No. The variable i is a count of how many elements you took, and the formula half = (total + 1) // 2 is what makes the median land on the left. Let's trace it.

Odd example — 5 elements total. half = (5 + 1) // 2 = 3. The left side gets 3 elements, the right side gets 2. The median of 5 elements is the 3rd one (position 2 in zero-indexed terms), which is the last element of the left partition — the biggest thing on the left.

merged (sorted):  [ 1,  2,  3,  4,  5 ]
                    ─────────  ──────
                     left (3)   right (2)
                          ↑
                     3rd element = median
                     = max of left side

The 3rd element is max(A_left, B_left) — whichever array contributed the last (largest) element to the left partition.

Even example — 6 elements total. half = (6 + 1) // 2 = 3. The left gets 3, the right gets 3. The median is the average of the 3rd and 4th elements, which is (max of left + min of right) / 2.

merged (sorted):  [ 1,  2,  3,  4,  5,  6 ]
                    ─────────  ──────────
                     left (3)    right (3)
                          ↑  ↑
                        3rd  4th  → median = (3 + 4) / 2

The mental model: half = (total + 1) // 2 is a deliberate choice to make the left partition one element fatter when the total is odd. That single extra element is the median. You don't need to look at the right side at all — the median is the biggest value sitting on the left, which is max(A_left, B_left).

But wait — i is an index into the right side, right? Yes, A[i] is the first element on the right. That doesn't matter. What matters is that A[i - 1] — the element just before the fence — is on the left. The fence counts how many you took, and half made you take one more than the other side. So the extra element (the median) ended up on the left, sitting at position i - 1 in one of the two arrays. You just don't know which array contributed it, so you take max(A_left, B_left) to find the larger of the two left-side boundary elements — and that is the median.

The solution ​

python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)   # (1)
        total = len(A) + len(B)
        half = (total + 1) // 2                                                  # (2)

        low, high = 0, len(A)                                                    # (3)

        while low <= high:
            i = low + (high - low) // 2        # (4) take i from A
            j = half - i                       # (5) so j from B is forced

            A_left  = A[i - 1] if i > 0        else float('-inf')    # (6)
            A_right = A[i]     if i < len(A)   else float('inf')
            B_left  = B[j - 1] if j > 0        else float('-inf')
            B_right = B[j]     if j < len(B)   else float('inf')

            if A_left <= B_right and B_left <= A_right:        # (7) correct cut
                if total % 2:                                  # (8)
                    return float(max(A_left, B_left))
                return (max(A_left, B_left) + min(A_right, B_right)) / 2

            if A_left > B_right:                               # (9)
                high = i - 1                   # took too much from A
            else:                                              # (10)
                low = i + 1                    # took too little

        return 0.0                                             # (11)
ts
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  const [A, B] = nums1.length <= nums2.length ? [nums1, nums2] : [nums2, nums1];  // (1)
  const total = A.length + B.length;
  const half = Math.floor((total + 1) / 2);                                       // (2)

  let low = 0, high = A.length;                                                   // (3)

  while (low <= high) {
    const i = low + Math.floor((high - low) / 2);   // (4)
    const j = half - i;                             // (5)

    const aLeft  = i > 0 ? A[i - 1] : -Infinity;    // (6)
    const aRight = i < A.length ? A[i] : Infinity;
    const bLeft  = j > 0 ? B[j - 1] : -Infinity;
    const bRight = j < B.length ? B[j] : Infinity;

    if (aLeft <= bRight && bLeft <= aRight) {       // (7)
      if (total % 2) return Math.max(aLeft, bLeft);  // (8)
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }

    if (aLeft > bRight) high = i - 1;               // (9)
    else low = i + 1;                               // (10)
  }

  return 0.0;                                       // (11)
}

Line by line ​

(1) Make A the shorter array. We only ever choose a cut position in A, and the cut in B follows from it. If A were the longer one, j = half - i could come out negative, or bigger than B's length, and we would need extra guards. Searching the shorter array means j always lands inside B.

(2) How many elements belong on the left. half = (total + 1) // 2 rounds up, so when the total is odd, the left side gets the one extra element. As explained above, that extra element is the median.

(3) The range of possible cuts in A. A cut can sit anywhere from "take nothing from A" (i = 0) to "take all of A" (i = len(A)). That is len(A) + 1 fence positions, so high starts at len(A), not len(A) - 1.

(4) Try taking i elements from A. This is the middle of the remaining range of cut positions.

(5) The cut in B is forced. The left side must hold exactly half elements. If i come from A, the other half - i must come from B.

(6) The four numbers next to the two cuts. A_left is the last number taken from A, and A_right is the first one left behind. The same goes for B. If a cut sits at the very edge of its array, one of these does not exist. We use minus infinity for a missing left number and plus infinity for a missing right number. Infinity always passes the comparison in line (7), so an edge cut is treated exactly like any other cut, with no extra if.

(7) Is this the correct cut? Within each array the order is already right, because both arrays are sorted. So we only need the two cross checks: the biggest number on A's left is not more than the smallest on B's right, and the biggest on B's left is not more than the smallest on A's right. If both hold, every number on the left is at most every number on the right.

(8) Read off the median. If the total is odd (total % 2 is 1), the median is the biggest number on the left: max(A_left, B_left). If it is even, the median is the average of the biggest on the left and the smallest on the right.

(9) A_left is too big. A number taken from A is bigger than a number left behind in B. We took too much from A, so move the cut in A to the left.

(10) Otherwise B_left is too big, which means we took too little from A. Move the cut in A to the right.

(11) Never reached. The arrays are sorted, so a correct cut always exists and line (7) always returns first. The line is there because the function must return something on every path.

Trace ​

A = [1, 3], B = [2]. A is already the shorter, total = 3, half = 2.

lowhighijA_leftA_rightB_leftB_rightverdict
0211132∞1 ≤ ∞ ✓ and 2 ≤ 3 ✓ — correct cut

Total is odd, so the median is max(A_left, B_left) = max(1, 2) = 2. ✓

The cut takes [1] from A and [2] from B on the left, leaving [3] on the right. The merged array is [1, 2, 3] and the median is 2.

Complexity ​

  • Time Complexity: O(\log(\min(m, n))). By ensuring A is the shorter array, our search space is the length of A, which is \min(m, n). Binary searching this range takes \log(\min(m, n)) steps. Inside the loop, all operations (indexing, comparing) are O(1). This strictly satisfies and actually beats the required O(\log(m+n)) bound.
  • Space Complexity: O(1) extra space. We only store a few pointer and value variables (low, high, i, j, A_left, etc.). We never actually build the merged array.

Edge cases ​

  • One array is empty, like A = [] and B = [2, 3]. A is the shorter, so high = 0 and the only cut is i = 0. Then A_left is minus infinity and A_right is plus infinity, both checks pass, and the median comes from B alone.
  • All of A is smaller than all of B, like [1, 2] and [3, 4]. The correct cut takes all of A, so A_right becomes plus infinity.
  • Equal numbers across the arrays, like [1, 1] and [1, 1]. The checks use <=, so equal numbers never block a correct cut.
  • An even total. Line (8) averages two numbers, so the answer can be a decimal like 2.5.

Being realistic about this problem ​

This is the hardest binary search commonly asked, and getting it perfect under pressure is unusual. Have a plan for partial credit.

Say the merge solution first: O(m+n), obviously correct, and it establishes that you understand the question. Then describe the cut idea in words — "the median is a cut where everything on the left is at most everything on the right, and choosing how much to take from one array forces the other" — even if the code does not come out perfectly. That description is most of the marks.

Where this goes next ​

  • Kth Smallest Element in Two Sorted Arrays — the same cut with half replaced by k. This problem is the special case k = (m+n+1)/2, which is a good way to remember it.
  • Kth Smallest in a Sorted Matrix — binary search on the value, counting how many entries fall below it. A different technique for a similar-sounding question, and worth contrasting.
  • Merging in general — the fence idea appears in external sorting and in parallel merge algorithms, where two threads must be given equal work without merging first.

What the interviewer will push on ​

"Why does j follow from i?" The left side must hold exactly half elements, so j = half - i.

"Why search the shorter array?" So that j always stays inside B's bounds.

"Why the infinities?" They make the boundary cases obey the same comparison as everything else, removing four branches.

"Why (total + 1) // 2?" It gives the extra element to the left side when the total is odd, so one formula covers both parities.

"Can you do it in O(m+n)?" Yes, by merging — and say that first, before attempting this.

One thing to volunteer: state the two laws before writing code. "The size law fixes j once I choose i; the ordering law is the two cross comparisons." Naming them is what turns this from a memorised trick into a derivation.

Next: 4.12 goes back to first principles on recursion — what the machine is doing, how to write a recurrence you can trust, and why backtracking is depth-first search over a tree you never build.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet