Problem Statement
Given two sorted arrays arr1[] and arr2[] and an integer k, return the kth smallest element from the combined sorted array.
Brute Force Intuition
In an interview, you can explain it like this:
Since both arrays are sorted, we can merge them similar to Merge Sort. While merging, keep counting elements. The moment we reach the kth element, return it.
Complexity
- Time Complexity: O(N + M)
- Space Complexity: O(N + M)
Brute Force Code
int[] merged = new int[n + m];
// Merge both arrays
return merged[k - 1];
Moving Towards the Optimal Approach
Notice something interesting:
For Median of Two Sorted Arrays, we partitioned arrays such that:
Left Half | Right Half
For Kth Element:
Exactly k elements must lie on the left side.
The partition idea remains exactly the same.
Pattern Recognition
Whenever you see:
- Two Sorted Arrays
- Kth Smallest Element
- Logarithmic Solution Expected
Think:
Binary Search on Partition
Key Observation
Suppose:
arr1 = [2,3,6,7,9]
arr2 = [1,4,8,10]
k = 5
We need:
Exactly 5 elements on left side
Partition:
2 3 6 | 7 9
1 4 | 8 10
Left Side:
1 2 3 4 6
contains exactly:
5 elements
Answer becomes:
max(left1, left2)
Optimal Approach
Let:
cut1 = elements taken from arr1
cut2 = k - cut1
Valid partition requires:
left1 <= right2
left2 <= right1
Once valid:
answer = Math.max(left1, left2);
Optimal Java Solution
class Solution {
public long kthElement(int k,
int arr1[],
int arr2[]) {
int n1 = arr1.length;
int n2 = arr2.length;
if (n1 > n2)
return kthElement(k, arr2, arr1);
int low = Math.max(0, k - n2);
int high = Math.min(k, n1);
while (low <= high) {
int cut1 = low + (high - low) / 2;
int cut2 = k - cut1;
int left1 =
cut1 == 0 ? Integer.MIN_VALUE
: arr1[cut1 - 1];
int left2 =
cut2 == 0 ? Integer.MIN_VALUE
: arr2[cut2 - 1];
int right1 =
cut1 == n1 ? Integer.MAX_VALUE
: arr1[cut1];
int right2 =
cut2 == n2 ? Integer.MAX_VALUE
: arr2[cut2];
if (left1 <= right2 &&
left2 <= right1) {
return Math.max(left1, left2);
}
else if (left1 > right2) {
high = cut1 - 1;
} else {
low = cut1 + 1;
}
}
return -1;
}
}
Dry Run
Input
arr1 = [2,3,6,7,9]
arr2 = [1,4,8,10]
k = 5
Need:
5 elements on left side
Partition:
2 3 6 | 7 9
1 4 | 8 10
Check:
6 <= 8 ✓
4 <= 7 ✓
Valid Partition.
Answer:
max(6,4)
= 6
Why This Works?
The kth element is simply:
Largest element among the first k elements
When partition is valid:
Left side contains exactly k elements.
Hence:
max(left1, left2)
becomes the kth element.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(log(min(N,M))) |
| Space Complexity | O(1) |
Interview One-Liner
Binary search the partition of the smaller array such that exactly k elements lie on the left side and both partitions remain sorted.
Pattern Learned
Two Sorted Arrays
+
Kth Element
+
Logarithmic Requirement
=> Binary Search on Partition
Similar Problems
- Median of Two Sorted Arrays
- Kth Element of Two Sorted Arrays
- Kth Smallest in Sorted Matrix
- Search in Rotated Array
Memory Trick
Think:
Median Problem
=
Half Elements on Left
Kth Element Problem
=
Exactly K Elements on Left
Mental Model
Median of Two Arrays
→ Partition at Half
Kth Element
→ Partition at K
Once you solve Median of Two Sorted Arrays, this problem is almost the same with just one change:
Half → K
That's the entire trick. 🚀