Find the Doubled Median of Two Sorted Arrays via Partitioning

Implement findDoubledMedian

Given two sorted arrays nums1 and nums2, find the median of all the elements combined — without necessarily merging them — returned as double its true value so the answer is always a whole number. Merging both arrays and reading off the middle works, but it does far more than necessary: only one or two values near the middle actually matter for the answer, yet the full combined array gets built regardless. The faster approach searches directly for a valid split point instead: a cut in the smaller array, paired with a matching cut in the larger one, such that together they divide all the elements into a "left half" and a "right half" of equal size, with every left value at most every right value. Binary search finds that cut in O(log(min(m,n))) guesses — checking just four boundary values per guess — and once a valid split is found, the median is read directly off those boundaries, with the merge step skipped entirely.

Example 1:

Input: nums1 = [3,9,15], nums2 = [6,12]

Output: 18

Example 2:

Input: nums1 = [4,10], nums2 = [1,7,13,19]

Output: 17

Example 3:

Input: nums1 = [1,2,3], nums2 = [4,5,6,7]

Output: 8

+ 3 hidden test cases run on Submit.

Constraints:

  • 1 ≤ nums1.length, nums2.length ≤ 6
  • -100 ≤ nums1[i], nums2[i] ≤ 200
  • Both arrays are sorted in non-decreasing order
  • Return double the true median, so the answer is always a whole number (avoiding any floating-point comparison)

nums1 =

[3, 9, 15]

nums2 =

[6, 12]