Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Median of Two Sorted Arrays

HARDProblemSolveExternal Links

Description

You are given two sorted arrays nums1 and nums2 of sizes m and n respectively. Your task is to find the median of the combined sorted array formed by merging both arrays.

The median is the middle value of a sorted list. If the total number of elements is odd, the median is the single middle element. If the total number is even, the median is the average of the two middle elements.

Important constraint: The overall runtime complexity must be O(log(m + n)).

In simpler terms: Imagine you have two stacks of numbered cards, each already arranged in ascending order. You want to find the value that would sit exactly in the middle if you merged both stacks into one sorted pile. The challenge is to do this efficiently without actually merging the entire pile.

Examples

Example 1

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

Output: 2.00000

Explanation: Merging both arrays gives [1, 2, 3]. The total length is 3 (odd), so the median is the middle element, which is 2.

Example 2

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

Output: 2.50000

Explanation: Merging gives [1, 2, 3, 4]. The total length is 4 (even), so the median is the average of the two middle elements: (2 + 3) / 2 = 2.5.

Example 3

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

Output: 1.00000

Explanation: One array is empty. The merged result is just [1], and the median of a single-element list is that element itself.

Example 4

Input: nums1 = [1, 3, 8, 9, 15], nums2 = [7, 11, 18, 19, 21, 25]

Output: 11.00000

Explanation: Merging gives [1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]. The total length is 11 (odd). The middle element at index 5 is 11.

Constraints

  • nums1.length == m
  • nums2.length == n
  • 0 ≤ m ≤ 1000
  • 0 ≤ n ≤ 1000
  • 1 ≤ m + n ≤ 2000
  • -10^6 ≤ nums1[i], nums2[i] ≤ 10^6
  • Both arrays are sorted in non-decreasing order
  • One or both arrays can be empty, but their combined length is at least 1

Editorial

Brute Force

Intuition

The most straightforward way to find the median is to combine both arrays into one, sort it, and then pick the middle element(s).

Think of it like having two separate piles of sorted exam papers. The simplest way to find the median score is to dump both piles together, re-sort everything from scratch, and then count to the middle. It works, but it ignores the fact that each pile was already sorted — you're throwing away useful information by re-sorting.

Step-by-Step Explanation

Let's trace through with nums1 = [1, 3], nums2 = [2]:

Step 1: Concatenate both arrays into a single array.

  • merged = [1, 3, 2]

Step 2: Sort the merged array.

  • merged = [1, 2, 3]

Step 3: Calculate total length.

  • total = 3 (odd number)

Step 4: Since total is odd, the median is at index total / 2 = 1.

  • median = merged[1] = 2

Step 5: Return 2.0.

Now let's also trace with nums1 = [1, 2], nums2 = [3, 4]:

Step 1: merged = [1, 2, 3, 4]

Step 2: Already sorted after concatenation (lucky case). merged = [1, 2, 3, 4].

Step 3: total = 4 (even number)

Step 4: The two middle indices are total/2 - 1 = 1 and total/2 = 2.

  • median = (merged[1] + merged[2]) / 2 = (2 + 3) / 2 = 2.5

Step 5: Return 2.5.

Brute Force — Merge, Sort, and Find Median — Watch how we concatenate both arrays, sort the result, and then locate the middle element(s) to compute the median.

Algorithm

  1. Create a new array by concatenating nums1 and nums2
  2. Sort the new array
  3. Let total = m + n
  4. If total is odd, return the element at index total / 2
  5. If total is even, return the average of elements at indices (total / 2 - 1) and (total / 2)

Code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> merged;
        merged.insert(merged.end(), nums1.begin(), nums1.end());
        merged.insert(merged.end(), nums2.begin(), nums2.end());
        sort(merged.begin(), merged.end());

        int total = merged.size();
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
};
class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        merged = sorted(nums1 + nums2)
        total = len(merged)

        if total % 2 == 1:
            return float(merged[total // 2])
        else:
            return (merged[total // 2 - 1] + merged[total // 2]) / 2.0
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, merged, 0, nums1.length);
        System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
        Arrays.sort(merged);

        int total = merged.length;
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
}

Complexity Analysis

Time Complexity: O((m + n) log(m + n))

We concatenate both arrays in O(m + n) time, then sort the merged array of size (m + n) using a comparison-based sort, which takes O((m + n) log(m + n)).

Space Complexity: O(m + n)

We create a new merged array of size m + n to hold all elements before sorting.

Why This Approach Is Not Efficient

The brute force approach takes O((m + n) log(m + n)) time due to the sorting step. While this works within the given constraints (m + n ≤ 2000), it completely ignores the fact that both input arrays are already sorted.

Sorting from scratch throws away valuable pre-existing order. Since both arrays are individually sorted, we should be able to leverage that structure. The problem statement explicitly requires O(log(m + n)) runtime — an exponential improvement over sorting.

The key insight: since both arrays are sorted, we can use a merge-like technique (similar to merge sort's merge step) to walk through both arrays simultaneously in linear time without sorting.

Better Approach - Merge Without Sorting

Intuition

Since both arrays are already sorted, we can merge them in order — just like the merge step of merge sort — by maintaining two pointers, one for each array. At each step, we pick the smaller of the two current elements.

But here is the clever part: we do not need to merge the entire arrays. We only need to find the middle element(s). So we can stop as soon as we have counted past the halfway point.

Imagine two queues of people arranged by height. To find the median height, you do not need to fully merge both queues. You just alternate picking the shorter person from the front of each queue until you reach the middle position.

Step-by-Step Explanation

Let's trace through with nums1 = [1, 2], nums2 = [3, 4]:

Step 1: Initialize two pointers i = 0, j = 0. Total = 4 (even), so we need elements at positions 1 and 2 (0-indexed).

Step 2: Count = 0. Compare nums1[0] = 1 vs nums2[0] = 3. Pick 1 (smaller). Move i to 1. Count = 1.

Step 3: Count = 1. Compare nums1[1] = 2 vs nums2[0] = 3. Pick 2 (smaller). Move i to 2. Count = 2. This is position 1 — save as m1 = 2.

Step 4: Count = 2. i = 2 is past nums1 end, so pick nums2[0] = 3. Move j to 1. Count = 3. This is position 2 — save as m2 = 3.

Step 5: We have both middle elements: m1 = 2, m2 = 3.

  • Median = (2 + 3) / 2 = 2.5

Step 6: Return 2.5.

Merge-Based Median — Two Pointer Walk — Watch how two pointers advance through both sorted arrays simultaneously, picking the smaller element each time, until we reach the middle position(s).

Algorithm

  1. Initialize two pointers i = 0 (for nums1) and j = 0 (for nums2)
  2. Track the two middle values m1 and m2 (both initialized to -1)
  3. Let total = m + n. The target positions are total/2 - 1 and total/2
  4. Iterate count from 0 to total/2:
    • Compare nums1[i] and nums2[j] (handle out-of-bounds cases)
    • Pick the smaller element, advance the corresponding pointer
    • Update m2 = m1, then m1 = picked element
  5. If total is odd, return m1
  6. If total is even, return (m1 + m2) / 2.0

Code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int total = m + n;
        int i = 0, j = 0;
        int m1 = -1, m2 = -1;

        for (int count = 0; count <= total / 2; count++) {
            m2 = m1;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                m1 = nums1[i++];
            } else {
                m1 = nums2[j++];
            }
        }

        if (total % 2 == 1) {
            return m1;
        }
        return (m1 + m2) / 2.0;
    }
};
class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        total = m + n
        i, j = 0, 0
        m1, m2 = -1, -1

        for count in range(total // 2 + 1):
            m2 = m1
            if i < m and (j >= n or nums1[i] <= nums2[j]):
                m1 = nums1[i]
                i += 1
            else:
                m1 = nums2[j]
                j += 1

        if total % 2 == 1:
            return float(m1)
        return (m1 + m2) / 2.0
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int i = 0, j = 0;
        int m1 = -1, m2 = -1;

        for (int count = 0; count <= total / 2; count++) {
            m2 = m1;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                m1 = nums1[i++];
            } else {
                m1 = nums2[j++];
            }
        }

        if (total % 2 == 1) {
            return m1;
        }
        return (m1 + m2) / 2.0;
    }
}

Complexity Analysis

Time Complexity: O(m + n)

We iterate through at most (m + n) / 2 + 1 elements, walking through both arrays once with two pointers. Each step does O(1) work (one comparison, one increment), so the total time is O(m + n).

Space Complexity: O(1)

We only use a constant number of variables (two pointers, two middle-value trackers). No additional data structures are created.

Why This Approach Is Not Efficient

The merge-based approach runs in O(m + n) time, which is a significant improvement over O((m+n) log(m+n)) sorting. However, the problem specifically asks for O(log(m + n)) complexity.

With m and n up to 1000, linear time is fast enough in practice. But conceptually, O(m + n) means we still examine up to half of all elements one by one. For very large arrays, this is wasteful.

The critical insight is: finding the median is equivalent to finding the correct partition point that divides all elements into a left half and a right half. In a sorted array, partitions can be found using binary search in logarithmic time. Since both arrays are sorted, we can binary search on one array to determine how many elements it contributes to the left half, and the other array's contribution is determined automatically.

Bar chart comparing O((m+n)log(m+n)) brute force, O(m+n) merge, and O(log(min(m,n))) binary search
Bar chart comparing O((m+n)log(m+n)) brute force, O(m+n) merge, and O(log(min(m,n))) binary search

Optimal Approach - Binary Search on Partition

Intuition

The median splits the combined sorted array into two equal halves. The left half contains the smaller (m + n) / 2 elements, and the right half contains the rest.

Here is the key realization: if we decide how many elements from nums1 go into the left half, the number from nums2 is automatically determined. For example, if the left half needs 5 elements total and we take 2 from nums1, we must take 3 from nums2.

So the problem reduces to: find the correct number of elements to take from nums1 for the left half. This is a classic binary search scenario — we can search over possible partition points in nums1 (from 0 to min(m, half)) and check if the partition is valid.

A partition is valid when:

  • The largest element on the left side of nums1 is ≤ the smallest element on the right side of nums2
  • The largest element on the left side of nums2 is ≤ the smallest element on the right side of nums1

In other words: everything in the left half must be ≤ everything in the right half. If the cross-conditions fail, we adjust our binary search bounds.

To minimize the search range, we always binary search on the shorter array. If nums1 is longer, we swap them so that we search over at most min(m, n) elements, giving us O(log(min(m, n))) time.

Diagram showing how partitioning both sorted arrays creates a valid left half and right half for the median
Diagram showing how partitioning both sorted arrays creates a valid left half and right half for the median

Step-by-Step Explanation

Let's trace with nums1 = [1, 3, 8, 9, 15], nums2 = [7, 11, 18, 19, 21, 25]:

Total = 11 (odd). Left half needs (11 + 1) / 2 = 6 elements. We binary search on nums1 (shorter array, m = 5).

Step 1: low = 0, high = 5. mid1 = (0 + 5) / 2 = 2. mid2 = 6 - 2 = 4.

  • Left from nums1: [1, 3]. Right from nums1: [8, 9, 15].
  • Left from nums2: [7, 11, 18, 19]. Right from nums2: [21, 25].
  • l1 = nums1[1] = 3, r1 = nums1[2] = 8.
  • l2 = nums2[3] = 19, r2 = nums2[4] = 21.
  • Check: l1 ≤ r2? 3 ≤ 21 → YES.
  • Check: l2 ≤ r1? 19 ≤ 8 → NO! We took too few from nums1.

Step 2: Since l2 > r1, move low = mid1 + 1 = 3.

  • low = 3, high = 5. mid1 = (3 + 5) / 2 = 4. mid2 = 6 - 4 = 2.
  • Left from nums1: [1, 3, 8, 9]. Right from nums1: [15].
  • Left from nums2: [7, 11]. Right from nums2: [18, 19, 21, 25].
  • l1 = nums1[3] = 9, r1 = nums1[4] = 15.
  • l2 = nums2[1] = 11, r2 = nums2[2] = 18.
  • Check: l1 ≤ r2? 9 ≤ 18 → YES.
  • Check: l2 ≤ r1? 11 ≤ 15 → YES.
  • Valid partition found!

Step 3: Total is odd, so median = max(l1, l2) = max(9, 11) = 11.

Result: Return 11.0.

Binary Search on Partition — Finding the Median Split — Watch how binary search narrows down the correct partition point in the shorter array, with the other array's partition determined automatically.

Algorithm

  1. Ensure nums1 is the shorter array. If not, swap nums1 and nums2.
  2. Let m = len(nums1), n = len(nums2), total = m + n.
  3. Compute half = (total + 1) / 2 (number of elements in the left partition).
  4. Set low = 0, high = m (binary search on nums1).
  5. While low ≤ high:
    a. mid1 = (low + high) / 2 — elements taken from nums1.
    b. mid2 = half - mid1 — elements taken from nums2.
    c. Compute boundary values:
    • l1 = nums1[mid1 - 1] if mid1 > 0, else -∞
    • l2 = nums2[mid2 - 1] if mid2 > 0, else -∞
    • r1 = nums1[mid1] if mid1 < m, else +∞
    • r2 = nums2[mid2] if mid2 < n, else +∞
      d. If l1 ≤ r2 AND l2 ≤ r1: valid partition found.
    • If total is odd: return max(l1, l2)
    • If total is even: return (max(l1, l2) + min(r1, r2)) / 2.0
      e. If l1 > r2: took too many from nums1 → high = mid1 - 1
      f. If l2 > r1: took too few from nums1 → low = mid1 + 1

Code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // Always binary search on the shorter array
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.size(), n = nums2.size();
        int total = m + n;
        int half = (total + 1) / 2;

        int low = 0, high = m;

        while (low <= high) {
            int mid1 = (low + high) / 2;
            int mid2 = half - mid1;

            int l1 = (mid1 > 0) ? nums1[mid1 - 1] : INT_MIN;
            int l2 = (mid2 > 0) ? nums2[mid2 - 1] : INT_MIN;
            int r1 = (mid1 < m) ? nums1[mid1] : INT_MAX;
            int r2 = (mid2 < n) ? nums2[mid2] : INT_MAX;

            if (l1 <= r2 && l2 <= r1) {
                if (total % 2 == 1) {
                    return max(l1, l2);
                }
                return (max(l1, l2) + min(r1, r2)) / 2.0;
            } else if (l1 > r2) {
                high = mid1 - 1;
            } else {
                low = mid1 + 1;
            }
        }

        return 0.0;
    }
};
class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        # Always binary search on the shorter array
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        total = m + n
        half = (total + 1) // 2

        low, high = 0, m

        while low <= high:
            mid1 = (low + high) // 2
            mid2 = half - mid1

            l1 = nums1[mid1 - 1] if mid1 > 0 else float('-inf')
            l2 = nums2[mid2 - 1] if mid2 > 0 else float('-inf')
            r1 = nums1[mid1] if mid1 < m else float('inf')
            r2 = nums2[mid2] if mid2 < n else float('inf')

            if l1 <= r2 and l2 <= r1:
                if total % 2 == 1:
                    return float(max(l1, l2))
                return (max(l1, l2) + min(r1, r2)) / 2.0
            elif l1 > r2:
                high = mid1 - 1
            else:
                low = mid1 + 1

        return 0.0
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Always binary search on the shorter array
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int half = (total + 1) / 2;

        int low = 0, high = m;

        while (low <= high) {
            int mid1 = (low + high) / 2;
            int mid2 = half - mid1;

            int l1 = (mid1 > 0) ? nums1[mid1 - 1] : Integer.MIN_VALUE;
            int l2 = (mid2 > 0) ? nums2[mid2 - 1] : Integer.MIN_VALUE;
            int r1 = (mid1 < m) ? nums1[mid1] : Integer.MAX_VALUE;
            int r2 = (mid2 < n) ? nums2[mid2] : Integer.MAX_VALUE;

            if (l1 <= r2 && l2 <= r1) {
                if (total % 2 == 1) {
                    return Math.max(l1, l2);
                }
                return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;
            } else if (l1 > r2) {
                high = mid1 - 1;
            } else {
                low = mid1 + 1;
            }
        }

        return 0.0;
    }
}

Complexity Analysis

Time Complexity: O(log(min(m, n)))

We binary search on the shorter of the two arrays. Each iteration halves the search space and does O(1) work (computing boundary values and comparing them). The total number of iterations is at most log₂(min(m, n)).

Since log(min(m, n)) ≤ log(m + n), this satisfies the problem's requirement of O(log(m + n)).

Space Complexity: O(1)

We use only a constant number of variables (low, high, mid1, mid2, l1, l2, r1, r2). No additional arrays or data structures are needed.