Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The first k merged elements consist of i elements from a and k − i from b, for some i.
  2. 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))
        break

Java 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