Skip to main content
Talentd

Median of Two Sorted Arrays - Solution & Explanation

HardArrayBinary SearchDivide and Conquer38 min readAsked at: Amazon, Microsoft, Apple +42
Practice this problem

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

 

Example 1:

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

Example 2:

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

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Approach Overview

Problem Overview: You are given two sorted arrays of sizes m and n. The goal is to compute the median of the combined sorted sequence without explicitly building the full merged array.

Approach 1: Merge and Find Median (O(m + n) time, O(1) or O(m+n) space)

This approach simulates the merge step from merge sort. Use two pointers to iterate through both arrays in sorted order until you reach the middle element of the combined length. If the total length is odd, the median is the middle value. If it is even, the median is the average of the two middle values. The idea is simple and reliable because both arrays are already sorted, but the algorithm still scans up to m + n elements.

This solution is useful when constraints are small or when you want a quick implementation during practice. It relies on sequential iteration over arrays and does not use advanced optimization.

Approach 2: Binary Search on Smaller Array (O(log(min(m,n))) time, O(1) space)

The optimal solution treats the problem as a partitioning task. Instead of merging arrays, perform binary search on the smaller array to find a partition such that the left halves of both arrays contain exactly half of the total elements. The key condition: the maximum element on the left side must be less than or equal to the minimum element on the right side.

During each step, choose a partition index in the smaller array and compute the corresponding partition in the second array. Check boundary values around the partitions. If the ordering condition fails, move the binary search window left or right. Once the correct partition is found, compute the median using the boundary elements.

This technique uses properties of sorted arrays and reduces the search space logarithmically. It combines ideas from arrays, binary search, and divide and conquer to achieve optimal performance.

Recommended for interviews: Interviewers typically expect the binary search partition solution with O(log(min(m,n))) time complexity. The merge approach demonstrates baseline understanding, but the partition method shows strong algorithmic reasoning and comfort with binary search edge cases.

Approach 1: Binary Search on Smaller Array

This approach leverages binary search to reduce the problem to a smaller size, achieving the desired O(log(m + n)) complexity. The strategy involves performing binary search on the smaller array to find the perfect partition point.

In this C solution, we first ensure that we perform the binary search on the smaller of the two arrays to maintain efficiency. We set bounds for `i` and adjust those bounds based on comparisons calculated at each step. The correct partitioning of elements between the two arrays determines the median.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(log(min(m,n))). Space complexity: O(1).

Try this approach in the editor →

Approach 2: Merge and Find Median

This approach focuses on merging the two sorted arrays as naturally done in merge sort, and then finding the median directly from the merged result. Though this solution has a higher time complexity, it's easier to implement and understand.

The C implementation uses an auxiliary array to merge the two sorted arrays into one. After merging, we calculate the median of the merged array based on its even or odd length. Memory allocation and deallocation are crucial to manage space efficiently.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(m + n). Space complexity: O(m + n).

Try this approach in the editor →

Approach 3: Divide and Conquer

The problem requires the time complexity of the algorithm to be O(log (m + n)), so we cannot directly traverse the two arrays, but need to use the binary search method.

If m + n is odd, then the median is the \left\lfloor\frac{m + n + 1}{2}\right\rfloor-th number; if m + n is even, then the median is the average of the \left\lfloor\frac{m + n + 1}{2}\right\rfloor-th and the \left\lfloor\frac{m + n + 2}{2}\right\rfloor-th numbers. In fact, we can unify it as the average of the \left\lfloor\frac{m + n + 1}{2}\right\rfloor-th and the \left\lfloor\frac{m + n + 2}{2}\right\rfloor-th numbers.

Therefore, we can design a function f(i, j, k), which represents the k-th smallest number in the interval [i, m) of array nums1 and the interval [j, n) of array nums2. The median is the average of f(0, 0, \left\lfloor\frac{m + n + 1}{2}\right\rfloor) and f(0, 0, \left\lfloor\frac{m + n + 2}{2}\right\rfloor).

The implementation idea of the function f(i, j, k) is as follows:

  • If i geq m, it means that the interval [i, m) of array nums1 is empty, so directly return nums2[j + k - 1];
  • If j geq n, it means that the interval [j, n) of array nums2 is empty, so directly return nums1[i + k - 1];
  • If k = 1, it means to find the first number, so just return the minimum of nums1[i] and nums2[j];
  • Otherwise, we find the \left\lfloor\frac{k}{2}\right\rfloor-th number in the two arrays, denoted as x and y. (Note, if a certain array does not have the \left\lfloor\frac{k}{2}\right\rfloor-th number, then we regard the \left\lfloor\frac{k}{2}\right\rfloor-th number as +infty.) Compare the size of x and y:
    • If x leq y, it means that the \left\lfloor\frac{k}{2}\right\rfloor-th number of array nums1 cannot be the k-th smallest number, so we can exclude the interval [i, i + \left\lfloor\frac{k}{2}\right\rfloor) of array nums1, and recursively call f(i + \left\lfloor\frac{k}{2}\right\rfloor, j, k - \left\lfloor\frac{k}{2}\right\rfloor).
    • If x > y, it means that the \left\lfloor\frac{k}{2}\right\rfloor-th number of array nums2 cannot be the k-th smallest number, so we can exclude the interval [j, j + \left\lfloor\frac{k}{2}\right\rfloor) of array nums2, and recursively call f(i, j + \left\lfloor\frac{k}{2}\right\rfloor, k - \left\lfloor\frac{k}{2}\right\rfloor).

The time complexity is O(log(m + n)), and the space complexity is O(log(m + n)). Here, m and n are the lengths of arrays nums1 and nums2 respectively.

Code

PythonJavaC++GoTypeScriptJavaScriptC#PHPNimC

Python

Java

C++

Go

TypeScript

JavaScript

C#

PHP

Nim

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search on Smaller Array

Time complexity: O(log(min(m,n))). Space complexity: O(1).

Merge and Find Median

Time complexity: O(m + n). Space complexity: O(m + n).

Divide and Conquer—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Merge and Find MedianO(m + n)O(1) or O(m+n)Simple implementation when constraints are small or during initial problem understanding
Binary Search on Smaller ArrayO(log(min(m,n)))O(1)Best choice for large inputs and expected solution in technical interviews

Video Solution

Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 724,399 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Median of Two Sorted Arrays easy or hard?
Median of Two Sorted Arrays is categorized as a hard problem because the optimal solution requires a non‑obvious binary search partition technique. Many candidates initially attempt a merge-based solution, but the interview expectation is the logarithmic binary search approach.
Median of Two Sorted Arrays Python/Java solution
Implementations typically follow the binary search partition method. The algorithm repeatedly adjusts the partition of the smaller array while computing the corresponding partition in the second array. Python, Java, C++, and JavaScript implementations all follow the same logic with constant extra space and O(log(min(m,n))) time.
What is the best approach for Median of Two Sorted Arrays?
The best approach uses binary search on the smaller array to find a valid partition between the two arrays. This method ensures the left half and right half of the combined arrays are correctly balanced. It runs in O(log(min(m,n))) time with O(1) extra space, making it the optimal solution for large inputs and interview settings.
Is Median of Two Sorted Arrays asked at Google/Amazon/Meta?
Median of Two Sorted Arrays is a well-known hard interview problem frequently associated with companies like Google, Amazon, and Meta. It tests binary search reasoning, handling edge cases, and understanding partition-based algorithms on sorted arrays.
What data structure is used in Median of Two Sorted Arrays?
The problem primarily uses arrays and binary search. The optimal solution manipulates partition indices within two sorted arrays and compares boundary elements to maintain ordering across the combined halves.
What is the time complexity of Median of Two Sorted Arrays?
The optimal algorithm runs in O(log(min(m,n))) time using a binary search partition strategy. A simpler approach merges both arrays and finds the middle element, which takes O(m + n) time. The binary search method is preferred because it reduces the search space dramatically.
How to solve Median of Two Sorted Arrays in O(log(min(m,n)))?
Perform binary search on the smaller array to choose a partition index. Compute the corresponding partition in the second array so the left halves contain half of the total elements. Adjust the search until the largest element on the left side is less than or equal to the smallest element on the right side. Once valid, compute the median from the boundary values around the partitions.

Ready to solve this problem?

Practice Median of Two Sorted Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of a Row Wise Sorted Matrix