K-th Element of Two Sorted Arrays

Medium
1397.

K-th Element of Two Sorted Arrays

K-th Element of Two Sorted Arrays is a medium coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google, Microsoft and Flipkart interviews.

Arrays a and b are each sorted in non-decreasing order. Imagine merging them into one sorted array of length a.length + b.length.

Return the element at position k (1-based) of that merged array — without building it.

Example 1

Input
a = [2,3,6,7,9], b = [1,4,8,10], k = 5
Output
6
Explanation
The merged array is 1, 2, 3, 4, 6, 7, 8, 9, 10.

Example 2

Input
a = [100,112,256,349,770], b = [72,86,113,119,265,445,892], k = 7
Output
256

Example 3

Input
a = [5], b = [5,5], k = 3
Output
5

Constraints

  • 1 <= a.length, b.length <= 10^6
  • 0 <= a[i], b[i] < 10^8
  • 1 <= k <= a.length + b.length
  • a and b are sorted in non-decreasing order
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} a
 * @param {number[]} b
 * @param {number} k
 * @return {number}
 */
var kthElement = function(a, b, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

K-th Element of Two Sorted Arrays — Problem & Solution

K-th Element of Two Sorted Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

K-th Element of Two Sorted Arrays is a medium coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google, Microsoft and Flipkart interviews.

Problem statement

Arrays a and b are each sorted in non-decreasing order. Imagine merging them into one sorted array of length a.length + b.length.

Return the element at position k (1-based) of that merged array — without building it.

Example 1

Input: a = [2,3,6,7,9], b = [1,4,8,10], k = 5
Output: 6
Explanation: The merged array is 1, 2, 3, 4, 6, 7, 8, 9, 10.

Example 2

Input: a = [100,112,256,349,770], b = [72,86,113,119,265,445,892], k = 7
Output: 256

Example 3

Input: a = [5], b = [5,5], k = 3
Output: 5

Constraints

  • 1 <= a.length, b.length <= 10^6
  • 0 <= a[i], b[i] < 10^8
  • 1 <= k <= a.length + b.length
  • a and b are sorted in non-decreasing order

Hints for K-th Element of Two Sorted Arrays

  1. Hint 1

    The first k merged elements consist of some prefix of a (say i elements) and some prefix of b (k - i elements).

  2. Hint 2

    A split i is right exactly when a[i-1] <= b[k-i] and b[k-i-1] <= a[i] (treat missing neighbours as -∞ / +∞).

  3. Hint 3

    Binary-search i over [max(0, k - b.length), min(k, a.length)]; the answer is max(a[i-1], b[k-i-1]) at the right split.

How to solve K-th Element of Two Sorted Arrays

Binary-search how many of the first k merged elements come from a. Each candidate split is checked by comparing the elements on either side of the cut in both arrays.

Approach

  1. Search the smaller array for speed: if a is longer, swap the arrays.
  2. Let lo = max(0, k - |b|), hi = min(k, |a|). While lo <= hi, set i = (lo + hi) / 2, j = k - i.
  3. Let L1 = a[i-1], R1 = a[i], L2 = b[j-1], R2 = b[j], using -∞/+∞ when an index falls off the end.
  4. If L1 <= R2 and L2 <= R1, return max(L1, L2). If L1 > R2, too many come from a: hi = i - 1. Otherwise lo = i + 1.

Why it works

When L1 <= R2 and L2 <= R1, every element in the two prefixes is <= every element after the cuts, so the prefixes are exactly the first k merged elements and their maximum is the k-th. If L1 > R2, an element of a inside the prefix is larger than one of b outside it, so fewer elements may come from a; symmetrically for the other case. Those monotone directions make the search valid.

Complexity

  • Time — O(log(min(|a|, |b|)))
  • Space — O(1)

Pitfalls

  • Bound i by both k - |b| and min(k, |a|) — otherwise j runs out of range.
  • Use sentinels below and above every value (here -1 and 2^31 - 1) for missing neighbours.
  • A linear two-pointer merge works too, but costs O(k).

Reference solution

Python

from typing import List

def kthElement(a: List[int], b: List[int], k: int) -> int:
    if len(a) > len(b):
        a, b = b, a
    n, m = len(a), len(b)
    lo, hi = max(0, k - m), min(k, n)
    while lo <= hi:
        i = (lo + hi) // 2
        j = k - i
        l1 = a[i - 1] if i > 0 else -1
        l2 = b[j - 1] if j > 0 else -1
        r1 = a[i] if i < n else 2147483647
        r2 = b[j] if j < m else 2147483647
        if l1 <= r2 and l2 <= r1:
            return max(l1, l2)
        if l1 > r2:
            hi = i - 1
        else:
            lo = i + 1
    return -1

Java

public static int kthElement(int[] a, int[] b, int k) {
    if (a.length > b.length) return kthElement(b, a, k);
    int n = a.length, m = b.length;
    int lo = Math.max(0, k - m), hi = Math.min(k, n);
    while (lo <= hi) {
        int i = (lo + hi) >>> 1, j = k - i;
        int l1 = i > 0 ? a[i - 1] : -1;
        int l2 = j > 0 ? b[j - 1] : -1;
        int r1 = i < n ? a[i] : Integer.MAX_VALUE;
        int r2 = j < m ? b[j] : Integer.MAX_VALUE;
        if (l1 <= r2 && l2 <= r1) return Math.max(l1, l2);
        if (l1 > r2) hi = i - 1; else lo = i + 1;
    }
    return -1;
}

C++

int kthElement(vector<int>& a, vector<int>& b, int k) {
    if (a.size() > b.size()) return kthElement(b, a, k);
    int n = a.size(), m = b.size();
    int lo = max(0, k - m), hi = min(k, n);
    while (lo <= hi) {
        int i = (lo + hi) / 2, j = k - i;
        int l1 = i > 0 ? a[i - 1] : -1;
        int l2 = j > 0 ? b[j - 1] : -1;
        int r1 = i < n ? a[i] : INT_MAX;
        int r2 = j < m ? b[j] : INT_MAX;
        if (l1 <= r2 && l2 <= r1) return max(l1, l2);
        if (l1 > r2) hi = i - 1; else lo = i + 1;
    }
    return -1;
}

JavaScript

var kthElement = function(a, b, k) {
    if (a.length > b.length) { var t = a; a = b; b = t; }
    var n = a.length, m = b.length;
    var lo = Math.max(0, k - m), hi = Math.min(k, n);
    while (lo <= hi) {
        var i = (lo + hi) >> 1, j = k - i;
        var l1 = i > 0 ? a[i - 1] : -1;
        var l2 = j > 0 ? b[j - 1] : -1;
        var r1 = i < n ? a[i] : 2147483647;
        var r2 = j < m ? b[j] : 2147483647;
        if (l1 <= r2 && l2 <= r1) return Math.max(l1, l2);
        if (l1 > r2) hi = i - 1; else lo = i + 1;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search