Solve the Hard-level Median of Two Sorted Arrays coding interview problem online in Python & JavaScript. Run your code against real test cases in the browser and study worked examples. It covers arrays, binary search, and divide and conquer. Read the step-by-step solution and complexity analysis. Java starter code is also included for reference (no in-browser JVM yet, so it can't be run here).

Median of Two Sorted Arrays – Solve Online in Python & JavaScript

Longest Valid Parentheses

Edit Distance

Find the combined median without fully merging two sorted arrays.

Given two ascending integer arrays, return the median of their combined values. At least one array is non-empty.

**Input / output**
- Input: `nums1: integer[]`, `nums2: integer[]`
- Output: floating-point median

**Examples**
1. `[1,3]` and `[2]` return `2.0`.
2. `[1,2]` and `[3,4]` return `2.5`.

**Constraints**
- `0 <= nums1.length, nums2.length <= 100,000`
- `1 <= nums1.length + nums2.length`
- Both arrays are sorted ascending

**Follow-up**
Can you partition the shorter array and achieve `O(log(min(m,n)))` time?

- The median splits the combined sorted values into a left half and a right half.
- Every value on the left must be less than or equal to every value on the right.
- If we can find that split without merging, we get logarithmic time.

Think in Terms of a Partition

- Choose how many values come from `nums1` on the left side, and infer how many must come from `nums2`.
- Searching the smaller array keeps the binary search range as small as possible and avoids invalid indexes.
- The left side should contain `(m + n + 1) // 2` values so odd lengths put the median on the left.

Binary Search the Smaller Array

- For a partition `i` in `nums1`, use `j = half - i` in `nums2`.
- Compare only four boundary values: left and right around each partition.
- Sentinels `-inf` and `inf` make empty sides easy to handle.

Check the Partition Boundaries

- A partition is valid when `left1 <= right2` and `left2 <= right1`.
- If `left1 > right2`, too many values were taken from `nums1`, so move left.
- Otherwise, too few values were taken from `nums1`, so move right.

Move Toward a Valid Split

- For odd total length, the median is the largest value on the left side.
- For even total length, average the largest left value and smallest right value.
- Time complexity is O(log(min(m, n))), and extra space complexity is O(1).