4. Median of Two Sorted Arrays
hardAsked at Juniper NetworksFind the median of two sorted arrays in O(log(m+n)) time using binary search on partition. Juniper asks this to probe candidates on binary search in non-obvious settings — the O(log n) constraint rules out the easy O(m+n) merge, requiring rigorous partitioning logic that appears in distributed query execution and sorted log analysis.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Juniper Networks loops.
- Glassdoor (2025-Q4)— Cited in Juniper senior SWE onsite reports as a binary search hard problem testing algorithmic rigor.
- Blind (2025-10)— Juniper threads list Median of Two Sorted Arrays as a hard problem asked in senior and staff engineering loops.
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.0Explanation: Merged: [1,2,3]. Median is 2.
Example 2
nums1 = [1,2], nums2 = [3,4]2.5Explanation: Merged: [1,2,3,4]. Median is (2+3)/2 = 2.5.
Approaches
1. Merge and find median — O(m+n)
Merge both arrays into a sorted array and return the middle element(s). Simple but does not meet the O(log(m+n)) requirement.
- 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: O(m+n) time and space. Easy to understand and verify. Mention this first to establish correctness, then optimize.
2. Binary search on partition — O(log(min(m,n)))
Binary search on the partition index in the smaller array. For a valid partition, the left half of both arrays combined must have (m+n)/2 elements, and max(left sides) <= min(right sides).
- Time
- O(log(min(m, n)))
- Space
- O(1)
function findMedianSortedArrays(nums1, nums2) {
// Always binary search on the smaller array
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length, n = nums2.length;
let lo = 0, hi = m;
while (lo <= hi) {
const partX = Math.floor((lo + hi) / 2); // partition in nums1
const partY = Math.floor((m + n + 1) / 2) - partX; // partition in nums2
const maxLeftX = partX === 0 ? -Infinity : nums1[partX - 1];
const minRightX = partX === m ? Infinity : nums1[partX];
const maxLeftY = partY === 0 ? -Infinity : nums2[partY - 1];
const minRightY = partY === n ? Infinity : nums2[partY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
// Correct partition
if ((m + n) % 2 === 1) return Math.max(maxLeftX, maxLeftY);
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
} else if (maxLeftX > minRightY) {
hi = partX - 1; // too far right in nums1
} else {
lo = partX + 1; // too far left in nums1
}
}
}Tradeoff: O(log(min(m,n))) time, O(1) space. The optimal solution meeting the O(log(m+n)) requirement. Complex to derive but the canonical answer for senior engineering roles.
Juniper Networks-specific tips
Acknowledge the two approaches upfront and their complexity difference. For senior Juniper roles, the binary search solution is expected — walk through the partition invariant carefully: 'I'm binary searching for a cut in nums1 such that the combined left halves are exactly half the total, and the maximum of the left sides is ≤ the minimum of the right sides.' Use Infinity and -Infinity as sentinels for edge partitions — it eliminates special cases cleanly.
Common mistakes
- Using +Infinity for maxLeft and -Infinity for minRight — the sentinel values are flipped: an empty left side has max = -Infinity, an empty right side has min = +Infinity.
- Not swapping to ensure binary search on the smaller array — the partition index in nums2 could go negative if m > n.
- Off-by-one in the partY formula — use (m + n + 1) / 2 (integer divide) to handle both odd and even total lengths with the same formula.
- Forgetting to handle the odd vs even total-length cases for the final median computation.
Follow-up questions
An interviewer at Juniper Networks may pivot to one of these next:
- Kth Largest Element in Two Sorted Arrays — binary search for the kth element instead of the median.
- How would you compute quantiles (p25, p50, p75) across two sorted telemetry streams efficiently?
- What if there are k sorted arrays instead of two?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why binary search on the smaller array?
partY = (m+n+1)/2 - partX. If m > n, partX can be large enough to make partY negative, which is invalid. Binary searching on the smaller array guarantees partY stays in [0, n].
Why use (m+n+1)/2 instead of (m+n)/2 in the partY formula?
The +1 ensures the left half is the same size or one larger for odd totals, giving the correct median without an extra conditional.
What are the sentinel values for?
-Infinity for an empty left side (no left elements exists, so the max is conceptually -∞) and +Infinity for an empty right side (no right element exists, so the min is conceptually +∞). This avoids special-casing boundary partitions.
Practice these live with InterviewChamp.AI
Drill Median of Two Sorted Arrays and other Juniper Networks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →