Find median of two sorted arrays
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates algorithmic problem-solving skills related to sorted arrays and median computation, testing competency in handling numeric order properties and complexity analysis within the Coding & Algorithms domain.
Constraints
- 0 <= len(nums1), len(nums2) <= 10^5
- len(nums1) + len(nums2) >= 1
- Each array is sorted in non-decreasing order
- Integer values fit in a 32-bit signed integer range
- Target time complexity: O(log(min(m, n)))
- Extra space complexity: O(1)
Examples
Input: ([1, 3], [2])
Expected Output: 2.0
Explanation: The combined sorted array would be [1, 2, 3], so the middle element is 2.
Input: ([1, 2], [3, 4])
Expected Output: 2.5
Explanation: The combined sorted array would be [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.
Input: ([], [1])
Expected Output: 1.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 values are both 0.
Input: ([-5, -3, -1], [-2])
Expected Output: -2.5
Explanation: The combined sorted array is [-5, -3, -2, -1], so the median is (-3 + -2) / 2 = -2.5.
Input: ([1, 2, 3, 4, 5], [6, 7, 8, 9, 10, 11])
Expected Output: 6.0
Explanation: The combined sorted array has 11 elements, so the median is the element at index 5, which is 6.
Solution
def solution(nums1, nums2):
if not nums1 and not nums2:
raise ValueError('At least one array must be non-empty')
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = (total + 1) // 2
left, right = 0, m
while left <= right:
i = (left + right) // 2
j = half - i
left1 = nums1[i - 1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j - 1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
if left1 <= right2 and left2 <= right1:
if total % 2 == 1:
return float(max(left1, left2))
return (max(left1, left2) + min(right1, right2)) / 2.0
elif left1 > right2:
right = i - 1
else:
left = i + 1
raise ValueError('Input arrays must be sorted in non-decreasing order')Time complexity: O(log(min(m, n))). Space complexity: O(1).
Hints
- Try binary searching on the smaller array instead of thinking about merging both arrays.
- A valid partition is one where every element on the left side is less than or equal to every element on the right side.