4. Median of Two Sorted Arrays - Explanation

Problem Link

Description

You are given two integer arrays nums1 and nums2 of size m and n respectively, where each is sorted in ascending order. Return the median value among all elements of the two arrays.

Your solution must run in O(log(m+n))O(log (m+n)) time.

Example 1:

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

Output: 2.0

Explanation: Among [1, 2, 3] the median is 2.

Example 2:

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

Output: 2.5

Explanation: Among [1, 2, 3, 4] the median is (2 + 3) / 2 = 2.5.

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • -10^6 <= nums1[i], nums2[i] <= 10^6


Topics

Array Binary Search Divide and Conquer

Recommended Time & Space Complexity

You should aim for a solution with O(log(min(n, m))) time and O(1) space, where n is the size of nums1 and m is the size of nums2.


Hint 1

A brute force solution would be to create a new array by merging elements from both arrays, then sorting it and returning the median. This would be an O(n + m) solution. Can you think of a better way? Maybe you can use the criteria of both the arrays being sorted in ascending order.


Hint 2

Suppose we merged both arrays. Then, we would have half = (m + n) / 2 elements to the left of the median. So, without merging, is there any way to use this information to find the median? You can leverage the fact that the arrays are sorted. Consider the smaller array between the two and use binary search to find the correct partition between the two arrays, which will allow you to directly find the median without fully merging the arrays. How will you implement this?


Hint 3

We will always try to keep array A smaller and interchange it with array B if len(A) > len(B). Now, we perform binary search on the number of elements we will choose from array A. It is straightforward that when we choose x elements from array A, we have to choose half - x elements from array B. But we should also ensure that this partition is valid. How can we do this?


Hint 4

When we do a partition for both arrays, we should ensure that the maximum elements from the left partitions of both arrays are smaller than or equal to the minimum elements of the right partitions of both the arrays. This will ensure that the partition is valid, and we can then find the median. We can find the min or max of these partitions in O(1) as these partitions are sorted in ascending order. Why does this work?


Hint 5

For example, consider the arrays A = [1, 2, 3, 4, 5] and B = [1, 2, 3, 4, 5, 6, 7, 8]. When we select x = 2, we take 4 elements from array B. However, this partition is not valid because value 4 from the left partition of array B is greater than the value 3 from the right partition of array A. So, we should try to take more elements from array A to make the partition valid. Binary search will eventually help us find a valid partition.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Binary Search - Efficiently searching in sorted data by eliminating half the search space
  • Two Pointers - Merging or comparing elements from two sorted arrays
  • Median Calculation - Understanding how to find the middle value(s) for odd and even length arrays
  • Array Partitioning - Conceptually dividing arrays to balance elements on left and right sides

1. Brute Force

Intuition

The simplest way to find the median of two sorted arrays is to combine them into one array and then sort it.
Once everything is merged and sorted, finding the median becomes straightforward:

  • If the total number of elements is odd → the middle element is the median.
  • If even → the median is the average of the two middle elements.

This method is easy to understand but does not take advantage of the fact that the input arrays are already sorted.

Algorithm

  1. Merge both arrays into a single list.
  2. Sort the merged list.
  3. Compute the total length:
    • If it’s odd, return the middle element.
    • If it’s even, return the average of the two middle elements.
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len1 = len(nums1)
        len2 = len(nums2)
        merged = nums1 + nums2
        merged.sort()

        totalLen = len(merged)
        if totalLen % 2 == 0:
            return (merged[totalLen // 2 - 1] + merged[totalLen // 2]) / 2.0
        else:
            return merged[totalLen // 2]

Time & Space Complexity

  • Time complexity: O((n+m)log⁡(n+m))O((n + m)\log (n + m))
  • Space complexity: O(n+m)O(n + m)

Where nn is the length of nums1nums1 and mm is the length of nums2nums2.

2. Two Pointers

Intuition

Since both arrays are already sorted, we don't need to fully merge them or sort again.
We can simulate the merge process using two pointers—just like in merge sort—but only advance until we reach the middle of the combined array.

Because the median depends only on the middle elements, we do not need to process the entire merged array.
We simply track the last one or two values seen while merging, and once we reach the halfway point, we can compute the median.

Algorithm

  1. Initialize two pointers i and j for each array.
  2. Iterate until you have processed (len1 + len2) // 2 + 1 elements:
    • At each step, pick the smaller of the two current elements.
    • Move the corresponding pointer forward.
    • Track the last two picked values (median1 and median2).
  3. After the loop:
    • If the total size is odd → return the last picked value (median1).
    • If even → return the average of the last two values ((median1 + median2) / 2).
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        len1, len2 = len(nums1), len(nums2)
        i = j = 0
        median1 = median2 = 0

        for count in range((len1 + len2) // 2 + 1):
            median2 = median1
            if i < len1 and j < len2:
                if nums1[i] > nums2[j]:
                    median1 = nums2[j]
                    j += 1
                else:
                    median1 = nums1[i]
                    i += 1
            elif i < len1:
                median1 = nums1[i]
                i += 1
            else:
                median1 = nums2[j]
                j += 1

        if (len1 + len2) % 2 == 1:
            return float(median1)
        else:
            return (median1 + median2) / 2.0

Time & Space Complexity

  • Time complexity: O(n+m)O(n + m)
  • Space complexity: O(1)O(1)

Where nn is the length of nums1nums1 and mm is the length of nums2nums2.

Intuition

Instead of fully merging the two arrays, think about this question:

“What is the k-th smallest element in the union of two sorted arrays?”

If we can find the k-th smallest element efficiently, then:

  • The median is just the middle element (or the average of the two middle elements).

To find the k-th smallest:

  • We compare the k/2-th element of each array.
  • The smaller one (and everything before it in that array) cannot be the k-th element,
    because there are at least k/2 elements smaller than or equal to it.
  • So we discard that many elements from one array and reduce k accordingly.
  • We repeat this process, shrinking the problem each time.

This is like a binary search on k: every step cuts off about half of the remaining elements, giving an O(log(k)) (or O(log(m + n))) solution.

Algorithm

  1. Define a function getKth(A, B, k) that returns the k-th smallest element in two sorted arrays A and B:

    1. Always make sure A is the shorter array (swap if needed).
    2. If A is empty, the k-th element is simply B[k-1].
    3. If k == 1, return min(A[0], B[0]).
    4. Let i = min(len(A), k/2) and j = min(len(B), k/2).
    5. Compare A[i-1] and B[j-1]:
      • If A[i-1] <= B[j-1], then the first i elements of A can't contain the k-th smallest.
        Call getKth(A[i:], B, k - i).
      • Else, the first j elements of B can't contain the k-th smallest.
        Call getKth(A, B[j:], k - j).

  2. To find the median:

    • Let total = len(A) + len(B).
    • If total is odd:
      • Median is getKth(A, B, (total + 1) / 2).
    • If total is even:
      • Median is the average of:
        • getKth(A, B, total / 2) and
        • getKth(A, B, total / 2 + 1).

  3. Return that median value.

class Solution:
    def get_kth(self, a: List[int], m: int, b: List[int], n: int, k: int, a_start: int = 0, b_start: int = 0) -> int:
        if m > n:
            return self.get_kth(b, n, a, m, k, b_start, a_start)
        if m == 0:
            return b[b_start + k - 1]
        if k == 1:
            return min(a[a_start], b[b_start])

        i = min(m, k // 2)
        j = min(n, k // 2)

        if a[a_start + i - 1] > b[b_start + j - 1]:
            return self.get_kth(a, m, b, n - j, k - j, a_start, b_start + j)
        else:
            return self.get_kth(a, m - i, b, n, k - i, a_start + i, b_start)

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        left = (len(nums1) + len(nums2) + 1) // 2
        right = (len(nums1) + len(nums2) + 2) // 2
        return (self.get_kth(nums1, len(nums1), nums2, len(nums2), left) +
                self.get_kth(nums1, len(nums1), nums2, len(nums2), right)) / 2.0

Time & Space Complexity

  • Time complexity: O(log⁡(m+n))O(\log (m + n))
  • Space complexity: O(log⁡(m+n))O(\log (m + n)) for recursion stack.

Where nn is the length of nums1nums1 and mm is the length of nums2nums2.

4. Binary Search (Optimal)

Intuition

We want the median of two sorted arrays without fully merging them.

Think of placing the two arrays side by side and making a cut (partition) so that:

  • The left side of the cut contains exactly half of the total elements (or half + 1 if odd).
  • All elements on the left side are <= all elements on the right side.

If we can find such a partition, then:

  • The median must come from the border elements around this cut:
    • The largest element on the left side,
    • And the smallest element on the right side.

To find this cut efficiently, we:

  • Only binary search on the smaller array.
  • For a chosen cut in the smaller array, the cut in the larger array is fixed (so total elements on the left is half).
  • Check if this partition is valid:
    • Aleft <= Bright and Bleft <= Aright
  • If not valid:
    • Move the cut left or right (like normal binary search) until it becomes valid.

Once we have a valid partition, we compute the median using the max of left side and min of right side.

Algorithm

  1. Let the two sorted arrays be A and B.
    Ensure A is the smaller array (swap if needed).

  2. Let:

    • total = len(A) + len(B)
    • half = total // 2

  3. Use binary search on A:

    • l = 0, r = len(A) - 1
    • While searching:
      • Let i be the cut index in A (midpoint of l and r).
      • Let j = half - i - 2 be the cut index in B
        (so that total elements on the left of both arrays equals half).

  4. Define border values around the cut:

    • Aleft = A[i] if i >= 0 else -∞
    • Aright = A[i + 1] if i + 1 < len(A) else +∞
    • Bleft = B[j] if j >= 0 else -∞
    • Bright = B[j + 1] if j + 1 < len(B) else +∞

  5. Check if the partition is valid:

    • If Aleft <= Bright and Bleft <= Aright:
      • We found the correct partition.
      • If total is odd:
        • Median = min(Aright, Bright)
      • Else (even total):
        • Median = (max(Aleft, Bleft) + min(Aright, Bright)) / 2
    • Else if Aleft > Bright:
      • Move the cut in A left → set r = i - 1.
    • Else (Bleft > Aright):
      • Move the cut in A right → set l = i + 1.

  6. Return the median computed from the valid partition.

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

        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

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

            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

Time & Space Complexity

  • Time complexity: O(log⁡(min(n,m)))O(\log (min(n, m)))
  • Space complexity: O(1)O(1)

Where nn is the length of nums1nums1 and mm is the length of nums2nums2.

Common Pitfalls

Binary Searching on the Larger Array

The binary search should be performed on the smaller array to ensure the partition index in the larger array stays within bounds. If you search on the larger array, the computed index j = half - i for the smaller array may become negative or exceed its length, causing index-out-of-bounds errors.

Incorrect Partition Index Calculation

A subtle bug arises from how you define the partition. Some implementations use half = (m + n) / 2 while others use half = (m + n + 1) / 2. Depending on this choice, the indices i and j and the formula for the median differ. Mixing conventions leads to off-by-one errors or incorrect median values.

Mishandling Edge Cases with Empty Partitions

When the partition places all elements of one array on one side (e.g., i = 0 or i = len(A)), the corresponding Aleft or Aright does not exist. You must use sentinel values like negative infinity and positive infinity for these boundary conditions. Accessing A[-1] or A[len(A)] directly causes runtime errors.

Confusing Odd and Even Total Length Cases

For odd total length, the median is a single element; for even, it is the average of two. The element(s) involved depend on whether you are taking the max of the left partition or the min of the right partition. Mixing up which elements to use for each case produces incorrect results.

Forgetting Arrays Are Already Sorted

Some implementations unnecessarily sort the input arrays or merge them fully before finding the median. This ignores the key constraint that the arrays are already sorted, inflating time complexity to O((m+n) log(m+n)) instead of the optimal O(log(min(m, n))).