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 (m+n)).

What to notice first

• Both input arrays are already sorted.
• You need to find the median, not just merge and sort.
• The challenge is to do this in logarithmic time, not linear time.
• The median of an array of length n is either the element at index n/2 (if n is odd) or the average of elements at indices n/2-1 and n/2 (if n is even).

Examples

nums1	nums2	Output	Explanation
[1, 3]	[2]	2.0	Merged array: [1, 2, 3]. Median is 2.
[1, 2]	[3, 4]	2.5	Merged array: [1, 2, 3, 4]. Median is (2 + 3) / 2 = 2.5
[]	[1]	1.0	Single element

Constraints

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

Where this pattern appears

• Array merging systems — Database engines merging sorted result sets from multiple indexes or partitions.
• Statistical computation — Real-time analytics processing continuous data streams where median is a key metric.
• Real-time data processing — Distributed systems computing running medians across multiple data sources without materializing the full dataset.
• Quantile estimation — Financial systems calculating median price, execution time, or latency across transactions and requests.

Complexity Comparison

Approach	Time	Space	Best When
Binary Search	O(log(min(m,n)))	O(1)	Optimal — logarithmic time
Two-Pointer	O(m + n)	O(1)	Simpler implementation

Which approach should you learn first?

• Pick Binary Search for the optimal O(log(min(m,n))) solution and interview preparation.
• Pick Two-Pointer if you want a simpler approach to understand the concept first.

Optimal

Binary Search

O(log(min(m,n))) time · O(1) space

Simpler

Two-Pointer

O(m + n) time · O(1) space

Approach 1: Binary Search (Recommended)

★ Recommended

Use binary search on the shorter array to find the partition point where the left half equals the right half in total length. This achieves O(log(min(m,n))) time.

⏱ Time O(log(min(m,n))) Binary search 💾 Space O(1) Constant

Solution Code

Python

median_sorted_arrays_binary_search.py

from typing import List

def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    """Binary search approach: O(log(min(m,n))) time, O(1) space"""
    if len(nums1) > len(nums2):
        return findMedianSortedArrays(nums2, nums1)

    m, n = len(nums1), len(nums2)
    left, right = 0, m

    while left <= right:
        partition1 = (left + right) // 2
        partition2 = (m + n + 1) // 2 - partition1

        left_max1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        right_min1 = float('inf') if partition1 == m else nums1[partition1]

        left_max2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        right_min2 = float('inf') if partition2 == n else nums2[partition2]

        if left_max1 <= right_min2 and left_max2 <= right_min1:
            if (m + n) % 2 == 0:
                return (max(left_max1, left_max2) + min(right_min1, right_min2)) / 2
            else:
                return max(left_max1, left_max2)
        elif left_max1 > right_min2:
            right = partition1 - 1
        else:
            left = partition1 + 1

    return -1.0

C++

median_sorted_arrays_binary_search.cpp

#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.size(), n = nums2.size();
    int left = 0, right = m;

    while (left <= right) {
        int partition1 = (left + right) / 2;
        int partition2 = (m + n + 1) / 2 - partition1;

        int left_max1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
        int right_min1 = (partition1 == m) ? INT_MAX : nums1[partition1];
        int left_max2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
        int right_min2 = (partition2 == n) ? INT_MAX : nums2[partition2];

        if (left_max1 <= right_min2 && left_max2 <= right_min1) {
            if ((m + n) % 2 == 0) {
                return (max(left_max1, left_max2) + min(right_min1, right_min2)) / 2.0;
            } else {
                return max(left_max1, left_max2);
            }
        } else if (left_max1 > right_min2) {
            right = partition1 - 1;
        } else {
            left = partition1 + 1;
        }
    }

    return -1.0;
}

Java

median_sorted_arrays_binary_search.java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length, n = nums2.length;
        int left = 0, right = m;

        while (left <= right) {
            int partition1 = (left + right) / 2;
            int partition2 = (m + n + 1) / 2 - partition1;

            int leftMax1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
            int rightMin1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];

            int leftMax2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
            int rightMin2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];

            if (leftMax1 <= rightMin2 && leftMax2 <= rightMin1) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(leftMax1, leftMax2) + Math.min(rightMin1, rightMin2)) / 2.0;
                } else {
                    return Math.max(leftMax1, leftMax2);
                }
            } else if (leftMax1 > rightMin2) {
                right = partition1 - 1;
            } else {
                left = partition1 + 1;
            }
        }

        return -1.0;
    }
}

System.out.println(new Solution().findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));

JavaScript

median_sorted_arrays_binary_search.js

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    const m = nums1.length, n = nums2.length;
    let left = 0, right = m;

    while (left <= right) {
        const partition1 = Math.floor((left + right) / 2);
        const partition2 = Math.floor((m + n + 1) / 2) - partition1;

        const left_max1 = partition1 === 0 ? -Infinity : nums1[partition1 - 1];
        const right_min1 = partition1 === m ? Infinity : nums1[partition1];
        const left_max2 = partition2 === 0 ? -Infinity : nums2[partition2 - 1];
        const right_min2 = partition2 === n ? Infinity : nums2[partition2];

        if (left_max1 <= right_min2 && left_max2 <= right_min1) {
            return (m + n) % 2 === 0 ?
                (Math.max(left_max1, left_max2) + Math.min(right_min1, right_min2)) / 2 :
                Math.max(left_max1, left_max2);
        } else if (left_max1 > right_min2) {
            right = partition1 - 1;
        } else {
            left = partition1 + 1;
        }
    }

    return -1.0;
}

Rust

median_sorted_arrays_binary_search.rs

pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    let (nums1, nums2) = if nums1.len() <= nums2.len() {
        (nums1, nums2)
    } else {
        (nums2, nums1)
    };

    let m = nums1.len();
    let n = nums2.len();
    let mut left = 0;
    let mut right = m;

    loop {
        let partition1 = (left + right) / 2;
        let partition2 = (m + n + 1) / 2 - partition1;

        let left_max1 = if partition1 == 0 { i32::MIN } else { nums1[partition1 - 1] };
        let right_min1 = if partition1 == m { i32::MAX } else { nums1[partition1] };
        let left_max2 = if partition2 == 0 { i32::MIN } else { nums2[partition2 - 1] };
        let right_min2 = if partition2 == n { i32::MAX } else { nums2[partition2] };

        if left_max1 <= right_min2 && left_max2 <= right_min1 {
            return if (m + n) % 2 == 0 {
                (left_max1.max(left_max2) as f64 + right_min1.min(right_min2) as f64) / 2.0
            } else {
                left_max1.max(left_max2) as f64
            };
        } else if left_max1 > right_min2 {
            right = partition1 - 1;
        } else {
            left = partition1 + 1;
        }
    }
}

Go

median_sorted_arrays_binary_search.go

package main

import "math"

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }

    m, n := len(nums1), len(nums2)
    left, right := 0, m

    for left <= right {
        partition1 := (left + right) / 2
        partition2 := (m + n + 1) / 2 - partition1

        left_max1 := math.MinInt32
        if partition1 != 0 { left_max1 = nums1[partition1-1] }
        right_min1 := math.MaxInt32
        if partition1 != m { right_min1 = nums1[partition1] }

        left_max2 := math.MinInt32
        if partition2 != 0 { left_max2 = nums2[partition2-1] }
        right_min2 := math.MaxInt32
        if partition2 != n { right_min2 = nums2[partition2] }

        if left_max1 <= right_min2 && left_max2 <= right_min1 {
            if (m+n)%2 == 0 {
                return float64(max(left_max1, left_max2)+min(right_min1, right_min2)) / 2.0
            } else {
                return float64(max(left_max1, left_max2))
            }
        } else if left_max1 > right_min2 {
            right = partition1 - 1
        } else {
            left = partition1 + 1
        }
    }

    return -1.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 }

Approach 2: Two-Pointer Merge

🎯 Interview Favourite

Merge both arrays while keeping track of the middle elements. This is linear time but easier to understand.

⏱ Time O(m + n) Linear merge 💾 Space O(1) Constant

Solution Code

Python

median_sorted_arrays_two_pointer.py

from typing import List

def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    """Two-pointer merge approach: O(m+n) time, O(1) space"""
    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

    merged.extend(nums1[i:])
    merged.extend(nums2[j:])

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

C++

median_sorted_arrays_two_pointer.cpp

#include <vector>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<int> merged;
    int i = 0, j = 0;

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

    while (i < nums1.size()) merged.push_back(nums1[i++]);
    while (j < nums2.size()) merged.push_back(nums2[j++]);

    int n = merged.size();
    return n % 2 == 1 ? merged[n / 2] : (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
}

Java

median_sorted_arrays_two_pointer.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> merged = new ArrayList<>();
        int i = 0, j = 0;

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

        while (i < nums1.length) {
            merged.add(nums1[i]);
            i++;
        }

        while (j < nums2.length) {
            merged.add(nums2[j]);
            j++;
        }

        int n = merged.size();
        if (n % 2 == 1) {
            return merged.get(n / 2);
        } else {
            return (merged.get(n / 2 - 1) + merged.get(n / 2)) / 2.0;
        }
    }
}

System.out.println(new Solution().findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));

JavaScript

median_sorted_arrays_two_pointer.js

function findMedianSortedArrays(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 n = merged.length;
    return n % 2 === 1 ? merged[Math.floor(n / 2)] :
        (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

Rust

median_sorted_arrays_two_pointer.rs

pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    let mut merged = Vec::new();
    let mut i = 0;
    let mut j = 0;

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

    while i < nums1.len() { merged.push(nums1[i]); i += 1; }
    while j < nums2.len() { merged.push(nums2[j]); j += 1; }

    let n = merged.len();
    if n % 2 == 1 {
        merged[n / 2] as f64
    } else {
        (merged[n / 2 - 1] + merged[n / 2]) as f64 / 2.0
    }
}

Go

median_sorted_arrays_two_pointer.go

package main

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    merged := []int{}
    i, j := 0, 0

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

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

    n := len(merged)
    if n%2 == 1 {
        return float64(merged[n/2])
    }
    return float64(merged[n/2-1]+merged[n/2]) / 2.0
}

Common mistakes

Watch for these pitfalls

• Off-by-one errors when calculating the median index.
• Not handling the case where one array is empty.
• Forgetting to handle the case when the total length is odd vs. even.
• Integer overflow when summing large numbers for the average.

Related Problems

• Find Median from Data Stream ↗ Hard #295
• Middle of the Linked List ↗ Easy #876

Interview Tips

Key points to discuss

• Why binary search? — Because both arrays are sorted, you can binary search on the shorter array to partition both arrays such that the left half and right half have equal length.
• The partition invariant — The key insight is: if you correctly partition, the maximum of the left half is less than the minimum of the right half.
• Why O(log(min(m,n)))? — You search on the shorter array, avoiding unnecessary comparisons when one array is much smaller.
• Edge cases: Empty arrays, odd vs. even total length, arrays of vastly different sizes.
• Follow-up: “Can you solve it without extra space?” — Both approaches already use O(1) space.
• Interview signal: Binary Search shows strong problem-solving skills; Two-Pointer demonstrates understanding of the merge concept.