Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays. The overall run time complexity should be O(log(min(m,n))).

Language Selection

Choose your preferred programming language

Showing: Python

Median of Two Sorted Arrays

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log(min(m,n))).

Examples

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
Explanation: The merged array is [1,2,3] and the median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5
Explanation: The merged array is [1,2,3,4] and the median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.0
Explanation: The merged array is [0,0,0,0] and the median is (0 + 0) / 2 = 0.

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.0
Explanation: The merged array is [1] and the median is 1.

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

Approach 1: Merge and Find Median

Algorithm Explanation

The straightforward approach merges both sorted arrays into one sorted array and then picks the median. While this does not meet the optimal time requirement, it is a useful starting point.

Steps:

  1. Merge the two sorted arrays using a two-pointer technique (like the merge step of merge sort).
  2. If the total length is odd, return the middle element.
  3. If the total length is even, return the average of the two middle elements.

Implementation

Python:

def findMedianSortedArrays(nums1, nums2):
    """
    Merge both arrays and find the median.
    Time: O(m + n)
    Space: O(m + n)
    """
    merged = []
    i, j = 0, 0

    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1

    while i < len(nums1):
        merged.append(nums1[i])
        i += 1

    while j < len(nums2):
        merged.append(nums2[j])
        j += 1

    total = len(merged)
    mid = total // 2

    if total % 2 == 1:
        return float(merged[mid])
    else:
        return (merged[mid - 1] + merged[mid]) / 2.0

Java:

class Solution {
    /**
     * Merge both arrays and find the median.
     * Time: O(m + n)
     * Space: O(m + n)
     */
    public double findMedianSortedArraysMerge(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;

        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];

        int total = m + n;
        int mid = total / 2;

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

Go:

// findMedianSortedArraysMerge merges both arrays and finds the median.
// Time: O(m + n), Space: O(m + n)
func findMedianSortedArraysMerge(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    merged := make([]int, 0, m+n)
    i, j := 0, 0

    for i < m && j < n {
        if nums1[i] <= nums2[j] {
            merged = append(merged, nums1[i])
            i++
        } else {
            merged = append(merged, nums2[j])
            j++
        }
    }

    for i < m {
        merged = append(merged, nums1[i])
        i++
    }
    for j < n {
        merged = append(merged, nums2[j])
        j++
    }

    total := m + n
    mid := total / 2

    if total%2 == 1 {
        return float64(merged[mid])
    }
    return float64(merged[mid-1]+merged[mid]) / 2.0
}

JavaScript:

/**
 * Merge both arrays and find the median.
 * Time: O(m + n)
 * Space: O(m + n)
 */
function findMedianSortedArraysMerge(nums1, nums2) {
    const merged = [];
    let i = 0, j = 0;

    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] <= nums2[j]) {
            merged.push(nums1[i++]);
        } else {
            merged.push(nums2[j++]);
        }
    }

    while (i < nums1.length) merged.push(nums1[i++]);
    while (j < nums2.length) merged.push(nums2[j++]);

    const total = merged.length;
    const mid = Math.floor(total / 2);

    if (total % 2 === 1) {
        return merged[mid];
    } else {
        return (merged[mid - 1] + merged[mid]) / 2;
    }
}

C#:

public class Solution {
    /// <summary>
    /// Merge both arrays and find the median.
    /// Time: O(m + n)
    /// Space: O(m + n)
    /// </summary>
    public double FindMedianSortedArraysMerge(int[] nums1, int[] nums2) {
        int m = nums1.Length, n = nums2.Length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;

        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];

        int total = m + n;
        int mid = total / 2;

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

Complexity Analysis

  • Time Complexity: O(m + n) – merges both arrays in a single pass.
  • Space Complexity: O(m + n) – stores the merged array.

Approach 2: Binary Search on the Shorter Array (Optimal)

Algorithm Explanation

The optimal approach uses binary search on the shorter of the two arrays to find the correct partition that divides the combined elements into two equal halves.

Core Idea:

  • We want to partition both arrays such that:
    • The left half contains exactly (m + n + 1) / 2 elements.
    • Every element in the left half is less than or equal to every element in the right half.

Definitions:

  • Let nums1 be the shorter array (length m) and nums2 be the longer (length n).
  • Binary search on i (the number of elements we take from nums1 for the left half), where 0 <= i <= m.
  • j = (m + n + 1) / 2 - i is the corresponding number of elements from nums2.

Partition Validity:

  • maxLeft1 <= minRight2 and maxLeft2 <= minRight1
  • Where maxLeft1 = nums1[i-1], minRight1 = nums1[i], maxLeft2 = nums2[j-1], minRight2 = nums2[j]
  • Handle boundary conditions with -infinity and +infinity.

Finding the Median:

  • If total length is odd: median = max(maxLeft1, maxLeft2)
  • If total length is even: median = (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2

Implementation

Python:

def findMedianSortedArrays(nums1, nums2):
    """
    Binary search on the shorter array to find the median partition.
    Time: O(log(min(m, n)))
    Space: O(1)
    """
    # Ensure nums1 is the shorter array
    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         # Partition index in nums2

        # Handle boundary values
        left1 = float('-inf') if i == 0 else nums1[i - 1]
        right1 = float('inf') if i == m else nums1[i]
        left2 = float('-inf') if j == 0 else nums2[j - 1]
        right2 = float('inf') if j == n else nums2[j]

        if left1 <= right2 and left2 <= right1:
            # Found the correct partition
            if (m + n) % 2 == 1:
                return float(max(left1, left2))
            else:
                return (max(left1, left2) + min(right1, right2)) / 2.0
        elif left1 > right2:
            # Too many elements from nums1 on the left; move left
            hi = i - 1
        else:
            # Too few elements from nums1 on the left; move right
            lo = i + 1

    return 0.0  # Should not reach here

Java:

class Solution {
    /**
     * Binary search on the shorter array to find the median partition.
     * Time: O(log(min(m, n)))
     * Space: O(1)
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the shorter array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

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

        int lo = 0, hi = m;

        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = half - i;

            int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (left1 <= right2 && left2 <= right1) {
                if ((m + n) % 2 == 1) {
                    return Math.max(left1, left2);
                } else {
                    return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
                }
            } else if (left1 > right2) {
                hi = i - 1;
            } else {
                lo = i + 1;
            }
        }

        return 0.0;
    }
}

Go:

import "math"

// findMedianSortedArrays finds the median using binary search on the shorter array.
// Time: O(log(min(m, n))), Space: O(1)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    // Ensure nums1 is the shorter array
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1
    }

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

    lo, hi := 0, m

    for lo <= hi {
        i := (lo + hi) / 2
        j := half - i

        left1 := math.MinInt64
        if i > 0 {
            left1 = nums1[i-1]
        }
        right1 := math.MaxInt64
        if i < m {
            right1 = nums1[i]
        }
        left2 := math.MinInt64
        if j > 0 {
            left2 = nums2[j-1]
        }
        right2 := math.MaxInt64
        if j < n {
            right2 = nums2[j]
        }

        if left1 <= right2 && left2 <= right1 {
            if (m+n)%2 == 1 {
                return float64(max(left1, left2))
            }
            return float64(max(left1, left2)+min(right1, right2)) / 2.0
        } else if left1 > right2 {
            hi = i - 1
        } else {
            lo = i + 1
        }
    }

    return 0.0
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

JavaScript:

/**
 * Binary search on the shorter array to find the median partition.
 * Time: O(log(min(m, n)))
 * Space: O(1)
 */
function findMedianSortedArrays(nums1, nums2) {
    // Ensure nums1 is the shorter array
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    const m = nums1.length, n = nums2.length;
    const half = Math.floor((m + n + 1) / 2);

    let lo = 0, hi = m;

    while (lo <= hi) {
        const i = Math.floor((lo + hi) / 2);
        const j = half - i;

        const left1 = i === 0 ? -Infinity : nums1[i - 1];
        const right1 = i === m ? Infinity : nums1[i];
        const left2 = j === 0 ? -Infinity : nums2[j - 1];
        const right2 = j === n ? Infinity : nums2[j];

        if (left1 <= right2 && left2 <= right1) {
            if ((m + n) % 2 === 1) {
                return Math.max(left1, left2);
            } else {
                return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
            }
        } else if (left1 > right2) {
            hi = i - 1;
        } else {
            lo = i + 1;
        }
    }

    return 0;
}

C#:

using System;

public class Solution {
    /// <summary>
    /// Binary search on the shorter array to find the median partition.
    /// Time: O(log(min(m, n)))
    /// Space: O(1)
    /// </summary>
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the shorter array
        if (nums1.Length > nums2.Length) {
            (nums1, nums2) = (nums2, nums1);
        }

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

        int lo = 0, hi = m;

        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = half - i;

            int left1 = (i == 0) ? int.MinValue : nums1[i - 1];
            int right1 = (i == m) ? int.MaxValue : nums1[i];
            int left2 = (j == 0) ? int.MinValue : nums2[j - 1];
            int right2 = (j == n) ? int.MaxValue : nums2[j];

            if (left1 <= right2 && left2 <= right1) {
                if ((m + n) % 2 == 1) {
                    return Math.Max(left1, left2);
                } else {
                    return (Math.Max(left1, left2) + Math.Min(right1, right2)) / 2.0;
                }
            } else if (left1 > right2) {
                hi = i - 1;
            } else {
                lo = i + 1;
            }
        }

        return 0.0;
    }
}

Complexity Analysis

  • Time Complexity: O(log(min(m, n))) – binary search on the shorter array.
  • Space Complexity: O(1) – only a constant number of variables.

Key Insights

  1. Binary Search on Partitions: Instead of searching for a specific value, we binary search for the correct partition point that divides the combined arrays into two equal halves.
  2. Always Search the Shorter Array: By binary searching on the shorter array, we guarantee O(log(min(m, n))) time. The partition index in the longer array is derived as j = half - i.
  3. Boundary Sentinels: Using -infinity and +infinity for out-of-bounds partition edges elegantly handles cases where all elements of one array are on the left or right side.
  4. Partition Validity: A valid partition satisfies maxLeft1 <= minRight2 and maxLeft2 <= minRight1. If maxLeft1 > minRight2, we took too many from nums1 and need to move left; vice versa.
  5. Odd vs Even Total: When the combined length is odd, the median is the maximum of the left partition. When even, it is the average of the maximum of the left partition and the minimum of the right partition.
  6. Why Not Just Merge?: Merging gives O(m + n), which is acceptable but not optimal. The binary search approach is asymptotically superior, especially when one array is much smaller than the other.

Edge Cases

  1. One Empty Array: nums1 = [], nums2 = [1] – the median is simply the median of the non-empty array.
  2. Arrays of Length 1: nums1 = [1], nums2 = [2] – median is (1 + 2) / 2 = 1.5.
  3. No Overlap: nums1 = [1,2], nums2 = [3,4] – arrays are disjoint.
  4. Full Overlap: nums1 = [1,3], nums2 = [2,4] – elements interleave perfectly.
  5. All Same Elements: nums1 = [0,0], nums2 = [0,0] – median is 0.
  6. Large Size Difference: nums1 = [1], nums2 = [2,3,4,5,6,7,8,9,10] – binary search on the much shorter array.
  7. Negative Numbers: nums1 = [-5,-3,-1], nums2 = [-2,0,4].

Test Cases

def test_findMedianSortedArrays():
    # Test case 1: Odd total length
    assert findMedianSortedArrays([1, 3], [2]) == 2.0

    # Test case 2: Even total length
    assert findMedianSortedArrays([1, 2], [3, 4]) == 2.5

    # Test case 3: One empty array
    assert findMedianSortedArrays([], [1]) == 1.0

    # Test case 4: One empty, even length
    assert findMedianSortedArrays([], [1, 2]) == 1.5

    # Test case 5: All zeros
    assert findMedianSortedArrays([0, 0], [0, 0]) == 0.0

    # Test case 6: Single elements
    assert findMedianSortedArrays([1], [2]) == 1.5

    # Test case 7: Disjoint arrays
    assert findMedianSortedArrays([1, 2], [3, 4, 5]) == 3.0

    # Test case 8: Negative numbers
    assert findMedianSortedArrays([-5, -3, -1], [-2, 0, 4]) == -1.5

    # Test case 9: Large size difference
    assert findMedianSortedArrays([1], [2, 3, 4, 5, 6]) == 3.5

    # Test case 10: Interleaving
    assert findMedianSortedArrays([1, 3, 5], [2, 4, 6]) == 3.5

    print("All tests passed!")

test_findMedianSortedArrays()

Common Mistakes

  1. Not Searching the Shorter Array: Binary searching the longer array still works but gives O(log(max(m, n))) instead of O(log(min(m, n))). Always swap so that nums1 is shorter.
  2. Off-by-One in Half Calculation: Using (m + n) / 2 instead of (m + n + 1) / 2 for the left partition size. The +1 ensures that for odd totals, the left partition gets the extra element.
  3. Boundary Index Errors: Forgetting to handle i = 0, i = m, j = 0, or j = n with sentinel values. Accessing nums1[-1] or nums2[n] causes index-out-of-bounds errors.
  4. Integer vs Float Return: Returning an integer when the median is a fractional value. Always use floating-point division for the even-length case.
  5. Wrong Search Direction: Moving lo up when left1 > right2 instead of moving hi down. When the left side of nums1 contributes too large a value, reduce i by moving hi = i - 1.

Interview Tips

  1. Start with the Merge Approach: Explain the O(m + n) merge solution first to demonstrate understanding, then optimize.
  2. Explain the Partition Concept: Draw both arrays and show how a partition divides the combined elements into two halves. This visual explanation is critical.
  3. Derive the Binary Search: Show why searching on the shorter array is sufficient and how j is computed from i.
  4. Handle Edge Cases Explicitly: Walk through what happens when one array is empty or when the partition is at the boundary.
  5. State the Complexity: O(log(min(m, n))) time and O(1) space. Emphasize that this is optimal for the problem.