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.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Divide and Conquer
- Asked at: Amazon, Google, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^60 <= a[i], b[i] < 10^81 <= k <= a.length + b.lengtha and b are sorted in non-decreasing order
Hints for K-th Element of Two Sorted Arrays
Hint 1
The first
kmerged elements consist of some prefix ofa(sayielements) and some prefix ofb(k - ielements).Hint 2
A split
iis right exactly whena[i-1] <= b[k-i]andb[k-i-1] <= a[i](treat missing neighbours as -∞ / +∞).Hint 3
Binary-search
iover[max(0, k - b.length), min(k, a.length)]; the answer ismax(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
- Search the smaller array for speed: if
ais longer, swap the arrays. - Let
lo = max(0, k - |b|),hi = min(k, |a|). Whilelo <= hi, seti = (lo + hi) / 2,j = k - i. - Let
L1 = a[i-1],R1 = a[i],L2 = b[j-1],R2 = b[j], using -∞/+∞ when an index falls off the end. - If
L1 <= R2andL2 <= R1, returnmax(L1, L2). IfL1 > R2, too many come froma:hi = i - 1. Otherwiselo = 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
iby bothk - |b|andmin(k, |a|)— otherwisejruns 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 -1Java
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