Find the Kth Element of Two Sorted Arrays
Introduction
Given two sorted arrays and an integer k, the task is to find the element that would appear at the kth position if both arrays were merged into a single sorted array.
The challenge is that the arrays can contain up to 10^6 elements, making it impractical to actually merge them.
Therefore, we need a more efficient solution.
Understanding the Problem
Consider:
a = [2, 3, 6, 7, 9]
b = [1, 4, 8, 10]
k = 5
Merged array:
[1, 2, 3, 4, 6, 7, 8, 9, 10]
The 5th element is:
6
Output:
6
Brute Force Approach
One straightforward method is:
Merge both arrays.
Sort the merged result.
Return the kth element.
Pseudo-code:
merge arrays
return merged[k-1]
Time Complexity
O(n + m)
Space Complexity
O(n + m)
Although acceptable for small inputs, this does not satisfy the expected logarithmic complexity.
Key Observation
Instead of finding the entire merged array, we only need the kth element.
This is similar to the famous Median of Two Sorted Arrays problem.
The idea is to divide both arrays into two parts such that:
Number of elements on the left side = k
Then the largest element on the left side becomes the answer.
Partition-Based Binary Search
Suppose:
cut1 = elements taken from array a
cut2 = k - cut1
Then:
Left Side
a[0 ... cut1-1]
b[0 ... cut2-1]
Right Side
remaining elements
We need a valid partition where:
leftMaxA <= rightMinB
and
leftMaxB <= rightMinA
Once this condition is satisfied:
answer = max(leftMaxA, leftMaxB)
because the left side contains exactly k elements.
Why Binary Search Works
Both arrays are sorted.
If:
leftMaxA > rightMinB
we have taken too many elements from array a.
Move left.
If:
leftMaxB > rightMinA
we have taken too few elements from array a.
Move right.
This allows binary search on the smaller array.
Algorithm
Always perform binary search on the smaller array.
Choose a partition in the first array.
Compute the corresponding partition in the second array.
Check partition validity.
Return the maximum value on the left side.
Java Solution
class Solution {
public int kthElement(int a[], int b[], int k) {
int n = a.length;
int m = b.length;
// Always binary search on smaller array
if (n > m) {
return kthElement(b, a, k);
}
int low = Math.max(0, k - m);
int high = Math.min(k, n);
while (low <= high) {
int cut1 = low + (high - low) / 2;
int cut2 = k - cut1;
int left1 = (cut1 == 0) ? Integer.MIN_VALUE : a[cut1 - 1];
int left2 = (cut2 == 0) ? Integer.MIN_VALUE : b[cut2 - 1];
int right1 = (cut1 == n) ? Integer.MAX_VALUE : a[cut1];
int right2 = (cut2 == m) ? Integer.MAX_VALUE : b[cut2];
if (left1 <= right2 && left2 <= right1) {
return Math.max(left1, left2);
}
if (left1 > right2) {
high = cut1 - 1;
} else {
low = cut1 + 1;
}
}
return -1;
}
}
Dry Run
Input
a = [2, 3, 6, 7, 9]
b = [1, 4, 8, 10]
k = 5
Since:
n > m
swap arrays.
Now:
a = [1, 4, 8, 10]
b = [2, 3, 6, 7, 9]
Try partition:
cut1 = 2
cut2 = 3
Left Side
1, 4
2, 3, 6
Right Side
8, 10
7, 9
Check:
max(left) = 6
Partition is valid.
Answer:
6
Another Example
Input
a = [1, 4, 8, 10, 12]
b = [5, 7, 11, 15, 17]
k = 6
Merged array:
[1, 4, 5, 7, 8, 10, 11, 12, 15, 17]
6th element:
10
Output:
10
Complexity Analysis
Binary search is performed only on the smaller array.
Time Complexity
O(log(min(n, m)))
Space Complexity
O(1)
Key Insight
Instead of merging two sorted arrays, we partition them so that exactly k elements lie on the left side. Once a valid partition is found, the largest element on the left side is precisely the kth element of the merged sorted order. This partition-based binary search technique reduces the complexity from linear time to logarithmic time, making it suitable for very large arrays.
Summary
Finding the kth element in two sorted arrays can be solved efficiently without merging the arrays. By applying a partition-based binary search on the smaller array, we ensure that exactly k elements remain on the left side of the partition. When the partition satisfies the ordering conditions, the maximum element on the left side becomes the answer. This approach achieves O(log(min(n, m))) time complexity and O(1) space complexity, making it ideal for handling very large datasets.