4. Median of Two Sorted Arrays
hardAsked at GleanGlean tests this to verify that candidates can reduce a tricky problem to binary search on the partition point — the same reasoning behind efficiently finding the rank-based cutoff in a dual-index search system without merging both indexes.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Glean loops.
- Glassdoor (2025-10)— Reported as an occasional hard in Glean senior-track onsites when the interviewer wants to test binary search fluency beyond simple sorted-array patterns.
- Blind (2025-07)— Glean SWE threads mention this problem as a potential hard for senior candidates; mid-level screens typically stop at merge-based solutions.
Problem
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)).
Constraints
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000−10^6 <= nums1[i], nums2[i] <= 10^6
Examples
Example 1
nums1 = [1,3], nums2 = [2]2.00000Explanation: Merged array = [1,2,3], median = 2.
Example 2
nums1 = [1,2], nums2 = [3,4]2.50000Explanation: Merged array = [1,2,3,4], median is (2+3)/2 = 2.5.
Approaches
1. Merge then find median (O(m+n))
Merge both sorted arrays using the two-pointer technique. Find the median from the merged array. This is O(m+n) time — not optimal but a valid starting point.
- Time
- O(m + n)
- Space
- O(m + n)
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 mid = Math.floor(merged.length / 2);
return merged.length % 2 === 1 ? merged[mid] : (merged[mid - 1] + merged[mid]) / 2;
}Tradeoff: Simple and correct but O(m+n) — doesn't meet the O(log(m+n)) requirement. Present this first to establish understanding, then optimize.
2. Binary search on partition (O(log(min(m,n))))
Binary search on the smaller array to find a partition point such that the left half of the combined partition contains exactly half the total elements, and all left elements ≤ all right elements. Use this to compute the median directly.
- Time
- O(log(min(m, n)))
- Space
- O(1)
function findMedianSortedArrays(nums1, nums2) {
// ensure nums1 is the shorter array
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length, n = nums2.length;
const half = Math.floor((m + n + 1) / 2); // left-half size
let lo = 0, hi = m;
while (lo <= hi) {
const i = Math.floor((lo + hi) / 2); // partition in nums1
const j = half - i; // partition in nums2
const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
const minRight1 = i === m ? Infinity : nums1[i];
const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
const minRight2 = j === n ? Infinity : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// correct partition
const maxLeft = Math.max(maxLeft1, maxLeft2);
if ((m + n) % 2 === 1) return maxLeft;
return (maxLeft + Math.min(minRight1, minRight2)) / 2;
} else if (maxLeft1 > minRight2) {
hi = i - 1; // too many elements from nums1 on the left
} else {
lo = i + 1; // too few elements from nums1 on the left
}
}
}Tradeoff: O(log(min(m,n))) time, O(1) space. The optimal solution — difficult to derive under pressure but highly impressive. Explain the partition invariant clearly before writing any code.
Glean-specific tips
Warn the interviewer upfront: 'The O(log(m+n)) solution is tricky — let me start with the O(m+n) merge approach to confirm correctness, then derive the binary-search partition.' Glean respects methodical thinking over rushed cleverness. The key insight to state: 'The median divides the combined array into two equal halves. I binary-search for the partition in the smaller array that satisfies this invariant.' Walk through the ±Infinity sentinels for edge cases — Glean interviewers probe edge case handling.
Common mistakes
- Not ensuring nums1 is the shorter array before binary search — the partition in nums2 must be non-negative; swapping guarantees this.
- Off-by-one in the half calculation — use (m + n + 1) / 2 (floor) so the left half is rounded up, which correctly handles both odd and even total lengths.
- Forgetting the -Infinity / Infinity sentinels for boundary partitions — without them, index 0 or index m partitions crash.
- Computing the median for odd total length incorrectly — when total is odd, the median is max(maxLeft1, maxLeft2); do not average.
Follow-up questions
An interviewer at Glean may pivot to one of these next:
- Kth Smallest Element in Two Sorted Arrays — generalize to finding the kth element rather than the median.
- What if you have K sorted arrays? Can the binary search approach extend?
- How does the approach change if the arrays are not fully sorted but nearly sorted?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why binary search on the smaller array?
The partition in nums2 is determined by the partition in nums1 (j = half - i). To ensure j stays in [0, n], i must be in [0, m] where m ≤ n. Binary searching the smaller array guarantees valid j values throughout.
What does the partition invariant mean exactly?
We want max(left half of nums1, left half of nums2) ≤ min(right half of nums1, right half of nums2). This means all elements to the left of both partitions are ≤ all elements to the right — exactly the split a median requires.
Practice these live with InterviewChamp.AI
Drill Median of Two Sorted Arrays and other Glean interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →