Practice › Binary Search
Kth Element of Two Sorted Arrays
Hard · Binary Search · Asked at Google, Amazon, Microsoft, Flipkart
Two arrays are sorted. Print the k-th smallest element (1-based) of their merged order, in O(log(min(n, m))).
Input
First line: n m k. Second line: the first array. Third line: the second array.
Output
The k-th smallest element.
Constraints
- 1 ≤ n, m ≤ 10^5
- 1 ≤ k ≤ n + m
- -10^9 ≤ values ≤ 10^9
Binary search how many elements (i) come from the first array; j = k − i come from the second. The split is right when a[i−1] ≤ b[j] and b[j−1] ≤ a[i].
Example 1
Input
5 4 5 2 3 6 7 9 1 4 8 10
Output
6
Example 2
Input
3 3 1 1 2 3 4 5 6
Output
1
Hints
- The first k merged elements consist of i elements from a and k − i from b, for some i.
- Binary search i (on the shorter array). The split is valid when a[i−1] ≤ b[k−i] and b[k−i−1] ≤ a[i]; the answer is then max(a[i−1], b[k−i−1]).
Approach
Make a the shorter array. i (taken from a) ranges over [max(0, k − m), min(k, n)]. For a guess i, let j = k − i and look at the four boundary values (use −∞/+∞ outside the arrays). If a[i−1] > b[j], too many come from a — move left. If b[j−1] > a[i], too few — move right. Otherwise the k-th element is the larger of a[i−1] and b[j−1].
Complexity: O(log(min(n, m))) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
long long k;
cin >> n >> m >> k;
vector<long long> a(n), b(m);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
if (n > m) swap(a, b), swap(n, m);
const long long NEG = LLONG_MIN, POS = LLONG_MAX;
long long lo = max(0LL, k - m), hi = min<long long>(k, n);
while (lo <= hi) {
long long i = (lo + hi) / 2, j = k - i;
long long aL = i > 0 ? a[i - 1] : NEG, aR = i < n ? a[i] : POS;
long long bL = j > 0 ? b[j - 1] : NEG, bR = j < m ? b[j] : POS;
if (aL > bR) hi = i - 1;
else if (bL > aR) lo = i + 1;
else {
cout << max(aL, bL) << "\n";
return 0;
}
}
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m, k = data[0], data[1], data[2]
a, b = data[3 : 3 + n], data[3 + n : 3 + n + m]
if n > m:
a, b, n, m = b, a, m, n
NEG, POS = float("-inf"), float("inf")
lo, hi = max(0, k - m), min(k, n)
while lo <= hi:
i = (lo + hi) // 2
j = k - i
aL = a[i - 1] if i > 0 else NEG
aR = a[i] if i < n else POS
bL = b[j - 1] if j > 0 else NEG
bR = b[j] if j < m else POS
if aL > bR:
hi = i - 1
elif bL > aR:
lo = i + 1
else:
print(max(aL, bL))
breakJava solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long k = sc.nextLong();
long[] a = new long[n], b = new long[m];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
for (int i = 0; i < m; i++) b[i] = sc.nextLong();
if (n > m) {
long[] t = a; a = b; b = t;
int x = n; n = m; m = x;
}
long lo = Math.max(0, k - m), hi = Math.min(k, n);
while (lo <= hi) {
int i = (int) ((lo + hi) / 2), j = (int) (k - i);
long aL = i > 0 ? a[i - 1] : Long.MIN_VALUE, aR = i < n ? a[i] : Long.MAX_VALUE;
long bL = j > 0 ? b[j - 1] : Long.MIN_VALUE, bR = j < m ? b[j] : Long.MAX_VALUE;
if (aL > bR) hi = i - 1;
else if (bL > aR) lo = i + 1;
else {
System.out.println(Math.max(aL, bL));
return;
}
}
}
}Solve Kth Element of Two Sorted Arrays online · All practice problems