Compute median of two sorted arrays
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two sorted arrays of integers `nums1` and `nums2`.
- `nums1` has length `m`, `nums2` has length `n`.
- Both arrays are sorted in non-decreasing order.
- Either array can be empty, but **not both** at the same time.
Your task is to find the **median** of the combined multiset formed by all elements of `nums1` and `nums2`.
- The overall run time complexity must be **O(log (m + n))**.
- You may not merge the two arrays into a third array of size `m + n` in a way that makes the complexity worse than \(O(m + n)\).
**Definition of median:**
- If `m + n` is odd, the median is the middle element after the two arrays' elements are conceptually merged and sorted.
- If `m + n` is even, the median is the average (as a floating point number) of the two middle elements after the two arrays' elements are conceptually merged and sorted.
**Function signature (conceptual):**
- Input: integer arrays `nums1`, `nums2`.
- Output: a floating point number representing the median.
**Examples:**
1. `nums1 = [1, 3]`, `nums2 = [2]` → merged is `[1, 2, 3]`, median = `2.0`.
2. `nums1 = [1, 2]`, `nums2 = [3, 4]` → merged is `[1, 2, 3, 4]`, median = `(2 + 3) / 2 = 2.5`.
Explain the algorithm you would use to achieve \(O(\log(m + n))\) time and its correctness, then implement it in code.
Quick Answer: This question evaluates algorithmic problem-solving with sorted arrays, focusing on concepts like binary search, partitioning strategies, complexity analysis, and careful handling of edge cases when computing order statistics.
You are given two sorted arrays of integers, nums1 and nums2, with lengths m and n. Both arrays are sorted in non-decreasing order, and at least one of them is non-empty. Return the median of the combined multiset formed by all elements of nums1 and nums2.
The solution must run in O(log(m + n)) time, so simply merging the arrays and then taking the middle is not sufficient for full credit.
Median definition:
- If m + n is odd, the median is the middle element of the combined sorted order.
- If m + n is even, the median is the average of the two middle elements, returned as a floating point number.
Constraints
- 0 <= len(nums1), len(nums2) <= 10^5
- 1 <= len(nums1) + len(nums2) <= 2 * 10^5
- -10^6 <= nums1[i], nums2[i] <= 10^6
- nums1 and nums2 are each sorted in non-decreasing order
Examples
Input: ([1, 3], [2])
Expected Output: 2.0
Explanation: The combined sorted array is [1, 2, 3], so the middle element is 2.
Input: ([1, 2], [3, 4])
Expected Output: 2.5
Explanation: The combined sorted array is [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.
Input: ([], [7])
Expected Output: 7.0
Explanation: Only one element exists in total, so that element is the median.
Input: ([0, 0], [0, 0])
Expected Output: 0.0
Explanation: The combined sorted array is [0, 0, 0, 0], and the two middle elements are both 0.
Input: ([-5, -3, -1], [2, 4, 6, 8])
Expected Output: 2.0
Explanation: The combined sorted array is [-5, -3, -1, 2, 4, 6, 8], so the middle element is 2.
Input: ([1, 2, 2], [2, 2, 3])
Expected Output: 2.0
Explanation: The combined sorted array is [1, 2, 2, 2, 2, 3], and the two middle elements are both 2.
Hints
- Try binary searching on the smaller array instead of thinking about positions in the merged array directly.
- Think of splitting both arrays into a left half and a right half such that every value on the left is less than or equal to every value on the right.