68. Median of Two Sorted Arrays
Find the middle value of all occurrences from both arrays when considered together in sorted order. With an even total size, return the average of the two middle values.
Keep duplicate occurrences and preserve both inputs. The optimized method must avoid merging the arrays into one complete sorted sequence.
Example 1
Input
a=[1,3], b=[2]
Output
2.0
Explanation: Search the shorter [2] array. A valid left partition contains ceil(3/2)=2 values; its maximum is the odd median.
Example 2
Input
a=[1,2], b=[3,4]
Output
2.5
Explanation: Partition [1,2] | [] on the left and [] | [3,4] on the right; middle values are 2 and 3.
Example 3
Input
a=[], b=[MIN,MAX]
Output
−0.5
Explanation: The empty shorter array has one possible cut. Widened (MIN+MAX)/2.0 is −0.5.
Example 4
Input
a=[MAX], b=[MAX]
Output
2,147,483,647.0
Explanation: Adding the middle values as int would overflow; long addition preserves the answer.
Constraints
0 <= a.length, b.length <= 105-231 <= a[i], b[i] <= 231 - 1- Both arrays are sorted in nondecreasing order. At least one array must be nonempty.
Hints
Hint 1
A median split puts ceil(total/2) values on the left, regardless of which array supplies them.
Hint 2
Choose i from the shorter array; the other cut j is fixed by the required left count.
Hint 3
Check aLeft<=bRight and bLeft<=aRight; move i away from a boundary that is too large, then read the middle value(s).
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Odd total searches the shorter array
[1,3]
[2]
2