To find the K-th smallest element in the union of two sorted arrays, we don't need to fully merge them. Instead, we use a binary search approach that narrows down the possible range efficiently.
Understanding the Problem
Imagine merging both arrays and sorting them. The K-th smallest element is simply the element at index k - 1
in this combined array. But instead of merging, we want to simulate this merging process using binary search on partitions.
General Strategy
We perform binary search on the smaller array to decide how many elements to take from it. Let’s say we take cut1
elements from arr1
, then we take k - cut1
elements from arr2
. The idea is to make sure all elements on the left side of the partition are less than or equal to all elements on the right side.
Different Scenarios
- Normal Case: Both arrays are non-empty. We can find the correct partition by comparing the left and right elements around the cut. The answer will be the maximum of the left halves of the partitions.
- Empty Array Case: If one array is empty, then the answer is simply the K-th element of the other array. For example, if
arr1 = []
and arr2 = [10, 20, 30]
, then the 2nd element is 20
.
- Out-of-Bounds K: If
k
is more than the total number of elements in both arrays, it’s invalid. In that case, we return -1
to indicate no such K-th element exists.
- Equal Lengths / Unbalanced Lengths: The algorithm works regardless of how balanced or unbalanced the array sizes are. It always searches in the smaller array to keep time complexity minimal.
Why Binary Search Works Here
Binary search reduces the number of comparisons by cutting the search space in half on every step. This makes the approach very efficient with a time complexity of O(log(min(n, m))), where n
and m
are the sizes of the two arrays.
This is much faster than merging the arrays, which takes O(n + m)
time and uses additional space. So this binary search approach is both time-efficient and space-efficient.