Log inSign up
hardleetcodeNot Started

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays in O(log (m+n)) time.

Binary Search
Solve on leetcode
Lesson

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 · Example 1: Odd Total Length:

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

Example 2 · Example 2: Even Total Length:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the optimal O(log(min(m,n))) median partition algorithm.
  • Handle even and odd combined parity seamlessly using (m + n + 1) / 2.
  • Manage empty array boundary conditions gracefully.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find median of two sorted arrays in O(log(m+n)).
  • Sorted partition dividing combined elements exactly in half.

Algorithmic Decision Tree:

  • Ensure m <= n.
  • low = 0, high = m.
  • cut1 = (low + high) / 2, cut2 = (m + n + 1) / 2 - cut1.
  • If l1 <= r2 and l2 <= r1 -> return median formula.
  • If l1 > r2 -> high = cut1 - 1.
  • Else -> low = cut1 + 1.

Connected Patterns:

Kth Element of Two Sorted ArraysBinary SearchSearch in Rotated Sorted Array

1. Merge and Find Median

Intuition

Allocate an array of size m+n. Merge nums1 and nums2 using two pointers. Return middle element if odd, or average of two middle elements if even.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Merge nums1 and nums2 into array merged of size m+n.
  2. Step 2: If (m+n) % 2 == 1 return merged[(m+n)/2].
  3. Step 3: Else return (merged[(m+n)/2 - 1] + merged[(m+n)/2]) / 2.0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
10 vector<int> merged;
11 int i = 0, j = 0;
12 while (i < (int)nums1.size() && j < (int)nums2.size()) {
13 if (nums1[i] <= nums2[j]) merged.push_back(nums1[i++]);
14 else merged.push_back(nums2[j++]);
15 }
16 while (i < (int)nums1.size()) merged.push_back(nums1[i++]);
17 while (j < (int)nums2.size()) merged.push_back(nums2[j++]);
18 int total = merged.size();
19 if (total % 2 == 1) return merged[total / 2];
20 return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(m + n) — Creates merged array of size m+n.
  • Space complexity: O(m + n) — O(m+n) auxiliary storage.

2. Two-Pointer Counting Without Extra Array

Intuition

Keep track of prev and curr elements as two pointers traverse up to (m+n)/2.

When to apply: When O(m+n) time is acceptable but O(1) space is required.

Algorithm

  1. Step 1: total = m + n, targetIdx = total / 2.
  2. Step 2: Advance pointers i and j, keeping track of prev and curr until index reaches targetIdx.
  3. Step 3: If total is odd return curr; else return (prev + curr) / 2.0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
10 int m = nums1.size(), n = nums2.size();
11 int total = m + n;
12 int idx2 = total / 2, idx1 = idx2 - 1;
13 int count = 0, i = 0, j = 0;
14 int el1 = 0, el2 = 0;
15 while (i < m && j < n) {
16 int val = (nums1[i] <= nums2[j]) ? nums1[i++] : nums2[j++];
17 if (count == idx1) el1 = val;
18 if (count == idx2) el2 = val;
19 count++;
20 }
21 while (i < m) {
22 int val = nums1[i++];
23 if (count == idx1) el1 = val;
24 if (count == idx2) el2 = val;
25 count++;
26 }
27 while (j < n) {
28 int val = nums2[j++];
29 if (count == idx1) el1 = val;
30 if (count == idx2) el2 = val;
31 count++;
32 }
33 if (total % 2 == 1) return el2;
34 return (el1 + el2) / 2.0;
35 }
36};
37
38int main() {
39 // Sample driver execution
40 cout << "Execution completed successfully." << endl;
41 return 0;
42}
43

Time & Space Complexity

  • Time complexity: O(m + n) — Traverses up to (m+n)/2 elements.
  • Space complexity: O(1) — O(1) auxiliary variables.

3. Binary Search on Partition Cut

Intuition

If nums1 is larger than nums2, swap them so m <= n. Search cut1 in [0, m]. cut2 = (m + n + 1) / 2 - cut1. Compute l1, l2, r1, r2. If l1 <= r2 and l2 <= r1, return median. If l1 > r2, high = cut1 - 1; else low = cut1 + 1.

When to apply: Standard optimal solution required in top tech interviews.

Algorithm

  1. Step 1: If nums1.length > nums2.length, swap arrays.
  2. Step 2: low = 0, high = m.
  3. Step 3: While low <= high:
  4. - cut1 = (low + high) / 2.
  5. - cut2 = (m + n + 1) / 2 - cut1.
  6. - l1 = (cut1 == 0) ? -INF : nums1[cut1 - 1].
  7. - l2 = (cut2 == 0) ? -INF : nums2[cut2 - 1].
  8. - r1 = (cut1 == m) ? +INF : nums1[cut1].
  9. - r2 = (cut2 == n) ? +INF : nums2[cut2].
  10. - If l1 <= r2 && l2 <= r1:
  11. * If (m + n) % 2 == 1 return max(l1, l2).
  12. * Else return (max(l1, l2) + min(r1, r2)) / 2.0.
  13. - If l1 > r2: high = cut1 - 1.
  14. - Else: low = cut1 + 1.

Trace for nums1 = [1, 3], nums2 = [2]

2 of 2 questions left today
Step 1 / 1
Trace timeline100% explored
Current operationSTEP 1 OF 1
nums1=[2] (len 1), nums2=[1, 3] (len 2)
Visual state
Values and pointers at this exact step
pointers
S
[2]
[1]
[3]
0
↑ cut1
1
↑ cut2
2
Check / comparison
l1(2) <= r2(3) && l2(1) <= r1(INF) -> Valid partition!
Decision / next transition
Return 2.0
Why this step matters

nums1=[2] (len 1), nums2=[1, 3] (len 2). Total=3, left size=(3+1)/2=2. cut1=1 (l1=2, r1=INF), cut2=2-1=1 (l2=1, r2=3). Check: l1(2) <= r2(3) TRUE, l2(1) <= r1(INF) TRUE. Odd length: median is max(l1, l2) = max(2, 1) = 2.0.

Step 1 / 1
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
10 if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
11 int m = nums1.size(), n = nums2.size();
12 int low = 0, high = m;
13 while (low <= high) {
14 int cut1 = (low + high) / 2;
15 int cut2 = (m + n + 1) / 2 - cut1;
16 int l1 = (cut1 == 0) ? INT_MIN : nums1[cut1 - 1];
17 int l2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1];
18 int r1 = (cut1 == m) ? INT_MAX : nums1[cut1];
19 int r2 = (cut2 == n) ? INT_MAX : nums2[cut2];
20 if (l1 <= r2 && l2 <= r1) {
21 if ((m + n) % 2 == 1) return max(l1, l2);
22 return (max(l1, l2) + min(r1, r2)) / 2.0;
23 } else if (l1 > r2) {
24 high = cut1 - 1;
25 } else {
26 low = cut1 + 1;
27 }
28 }
29 return 0.0;
30 }
31};
32
33int main() {
34 // Sample driver execution
35 cout << "Execution completed successfully." << endl;
36 return 0;
37}
38

Time & Space Complexity

  • Time complexity: O(log(min(m, n))) — Binary search takes log2(min(m, n)) steps.
  • Space complexity: O(1) — Requires O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Merge and Find MedianO(m + n)O(m + n)Full merge into new array.Full merge traversal.
2.Two-Pointer CountingO(m + n)O(1)Count elements up to middle without storing.Traverses half of total elements.
3.Binary Search on Partition CutOptimalO(log(min(m, n)))O(1)Partition smaller array using binary search.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • One array is empty (m == 0 or n == 0).
  • Total length is 1.
  • All elements of nums1 are smaller than nums2.
  • Arrays with negative numbers and duplicates.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why searching on the smaller array avoids out-of-bounds index calculations on the larger array.
  2. Walk through why (m + n + 1) / 2 works for both odd and even parity.
  3. Emphasize the floating point division (return double/float) for even lengths.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we use (m + n + 1) / 2 for the left partition size?

Back to DSA Sheet