Median of Two Sorted Arrays

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).