22. Median of Two Sorted Arrays
hardAsked at SwiggyMedian of Two Sorted Arrays is the classic logarithmic-time partition problem: given two already-sorted arrays, return the median of their combined order without actually merging them. Swiggy candidates report it in senior late-loop rounds, where the interviewer is less interested in the final code than in whether you can derive and defend the partition invariant — the same robust-statistics thinking behind p50 delivery-time metrics that a food-delivery platform lives on.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Swiggy loops.
- LeetCode (2026)— Problem #4 'Median of Two Sorted Arrays' — canonical statement, constraints, and the O(log(m+n)) follow-up requirement.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Swiggy interview prep.
Problem
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays as if they were merged into one sorted array. The overall run time complexity should be O(log(m+n)) — linear merging is the baseline, not the answer.
Constraints
0 <= m, n <= 10001 <= m + n <= 2000-10^6 <= nums[i] <= 10^6Either array may be empty — the sentinel-based partition must handle i = 0 and i = m cleanly.
Examples
Example 1
nums1=[1,3], nums2=[2]2.0Explanation: Merged order is [1,2,3]; the combined length is odd, so the median is the single middle element 2.
Example 2
nums1=[1,2], nums2=[3,4]2.5Explanation: Merged order is [1,2,3,4]; even length, so the median averages the two middle elements: (2 + 3) / 2 = 2.5.
Approaches
1. Merge then index
Merge the two sorted arrays then read median position.
- Time
- O(m+n)
- Space
- O(m+n)
const m=[...nums1,...nums2].sort((a,b)=>a-b);
const k=m.length;
return k%2 ? m[(k-1)/2] : (m[k/2-1]+m[k/2])/2;Tradeoff: Linear time and space, and it ignores that the inputs are already sorted. It is the correct warm-up to state for correctness, but stopping here on a hard-rated question reads as not knowing the binary-search partition exists.
2. Binary search partition
Binary search on the smaller array to choose a partition so left halves combine to floor((m+n+1)/2) elements with max(left) <= min(right). The median falls at the boundary.
- Time
- O(log(min(m,n)))
- Space
- O(1)
function findMedianSortedArrays(A, B) {
if (A.length > B.length) [A, B] = [B, A];
const m = A.length, n = B.length;
const half = Math.floor((m + n + 1) / 2);
let lo = 0, hi = m;
while (lo <= hi) {
const i = (lo + hi) >> 1;
const j = half - i;
const aL = i === 0 ? -Infinity : A[i - 1];
const aR = i === m ? Infinity : A[i];
const bL = j === 0 ? -Infinity : B[j - 1];
const bR = j === n ? Infinity : B[j];
if (aL <= bR && bL <= aR) {
if ((m + n) % 2) return Math.max(aL, bL);
return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
} else if (aL > bR) hi = i - 1;
else lo = i + 1;
}
}Tradeoff: Logarithmic in the smaller array with O(1) space — the expected answer. The cost is conceptual: four boundary values, two sentinel infinities, and an invariant you must be able to restate when the interviewer asks 'why is that partition correct?' Practice saying it, not just typing it.
Swiggy-specific tips
Swiggy candidates report this appearing in senior late-loop rounds, and the signal being graded is invariant articulation: say 'left halves together hold floor((m+n+1)/2) elements, and every left element must be <= every right element' before writing any code. Tie it to the domain if invited — a delivery platform reasons in medians and percentiles (p50 ETA, median order value) because they are robust to outliers, unlike means. Always binary-search the smaller array and walk one worked example aloud, e.g. [1,3] and [2].
Common mistakes
- Binary searching the larger array — j = half - i can then go negative or past the end, crashing the partition bounds.
- Dropping the +1 in half = floor((m+n+1)/2) — odd totals then put the median on the wrong side of the partition.
- Skipping the -Infinity / +Infinity sentinels at i = 0, i = m, j = 0, j = n — empty-side partitions are exactly where hard test cases live.
- Returning an integer for even totals instead of the .5 average — the answer type is a float, and interviewers notice the sloppy return.
Follow-up questions
An interviewer at Swiggy may pivot to one of these next:
- Generalize to the k-th smallest element of two sorted arrays — the same partition argument with half replaced by k.
- Median of k sorted arrays — pairwise partitioning stops scaling; discuss a heap-based or binary-search-on-value approach.
- Find Median from Data Stream (LC 295) — the streaming variant using two heaps, a natural follow-up for metrics pipelines.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why binary search the smaller array specifically?
It guarantees j = half - i always lands inside the larger array's valid range, so only one search variable needs bounds-checking. It also makes the runtime O(log(min(m,n))), which is strictly better than O(log(m+n)).
Why does max(left) <= min(right) prove the partition is correct?
Both arrays are sorted, so the only cross-array orderings that could break the merged order are aL > bR or bL > aR. If neither holds, every left-half element is <= every right-half element — which is exactly the definition of a median split.
Can you do better than O(log(min(m,n)))?
Not meaningfully — any comparison-based method must narrow down the median's position, which needs logarithmic probing. Constant time is impossible without stronger assumptions about the value distribution.