Median of Two Sorted Arrays

Question

Given two sorted arrays, find their median in O(log(min(m,n))) time. A classic binary search problem that tests divide-and-conquer thinking, frequently asked at Google.

Codemia · Accepted Answer

The problem at hand is to find the median of two sorted arrays, which can be solved efficiently using a binary search approach. The key observation is that the median divides the combined arrays into two halves. To utilize the binary search effectively, we can perform the search on the smaller of the two arrays. This allows us to minimize the search space, leading to an O(log(min(m,n))) time complexity, where m and n are the sizes of the two arrays. 1. Identify the shorter array (let's call it `A`) and the longer array (`B`). 2. Initialize binary search on the shorter array `A`. 3. Define two pointers, `left` and `right`, to represent the current search bounds in `A`. 4. Calculate the partition index for both arrays. The partition index for `A` will be `i` and for `B` will be `j`, where `i + j = (m + n + 1) // 2`. 5. Check if the current partition indices satisfy the median conditions: - `A[i-1] <= B[j]` (ensuring the left partition of A is less than or equal to the right partition of B) - `B[j-1] <= A[i]` (ensuring the left partition of B is less than or equal to the right partition of A) 6. If the conditions are not satisfied, adjust the binary search indices accordingly: - If `A[i-1] > B[j]`, move `right` to `i - 1`. - If `B[j-1] > A[i]`, move `left` to `i + 1`. 7. When conditions are satisfied, calculate the median based on the size of the combined arrays. If the total length is even, return the average of the two middle values; if odd, return the maximum of the left partition. ```python def findMedianSortedArrays(nums1, nums2): # Ensure nums1 is the smaller array if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 x, y = len(nums1), len(nums2) low, high = 0, x while low <= high: partitionX = (low + high) // 2 partitionY = (x + y + 1) // 2 - partitionX # If partitionX is 0 it means nothing is there on left side. Use -inf for maxLeftX # If partitionX is length of input then there is nothing on right side. Use +inf for minRightX maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1] minRightX = float('inf') if partitionX == x else nums1[partitionX] maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1] minRightY = float('inf') if partitionY == y else nums2[partitionY] if maxLeftX <= minRightY and maxLeftY <= minRightX: # We have partitioned array at correct place if (x + y) % 2 == 0: return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2 else: return max(maxLeftX, maxLeftY) elif maxLeftX > minRightY: high = partitionX - 1 else: low = partitionX + 1 ``` The time complexity of the solution is O(log(min(m, n))) because we are performing a binary search on the smaller array. The space complexity is O(1) since we are using a constant amount of space for variables, regardless of the input size. 1. One or both arrays are empty: If `nums1` is empty, return the median of `nums2`. If both are empty, handle as an invalid input. 2. Both arrays contain the same element: This will still yield the correct median as the partitions will align properly. 3. Arrays with odd/even total length: Ensure correct handling in calculation based on whether the combined length of the arrays is odd or even.

Median of Two Sorted Arrays

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string