DSA interview question

K-th Element of Two Sorted Arrays

Medium · Algorithms · Topics: binary search, array

The problem

Two exam boards each publish a sorted list of scores, and a scholarship committee needs the k-th smallest score across both lists to set its cut-off, without merging millions of records. It's the generalisation of the median problem: instead of a left half of size ⌈(m + n)/2⌉, the left part must contain exactly k elements. Binary search how many of those come from the first array, with bounds adjusted so neither array is asked for more elements than it has.

Example: [2, 3, 6, 7, 9] and [1, 4, 8, 10], k = 5 → 6.

Function signature

int kthElement(const vector<int>& a, const vector<int>& b, int k);  // 1 <= k <= m + n

Test cases

Input `(a, b, k)`	Output	Explanation
`([2, 3, 6, 7, 9], [1, 4, 8, 10], 5)`	6	Merged: 1, 2, 3, 4, 6, ...
`([100, 112, 256, 349, 770], [72, 86, 113, 119, 265, 445, 892], 7)`	256
`([1], [2], 1)`	1
`([1], [2], 2)`	2
`([], [1, 2, 3], 2)`	2	One array empty

(Confirm: both arrays are sorted; k is 1-indexed and valid.)

How interviewers phrase it

"Find the k-th element of two sorted arrays" (GeeksforGeeks).
A generalisation of "median of two sorted arrays", often asked straight after it.

Clarifying questions to ask

Is k 1-indexed?
Can one array be empty?
Is O(log(min(m, n))) required, or is O(k) acceptable?

Follow-ups to expect

"What's the simple approach?"
"What changes from the median version?"
"What's the answer once the partition is right?"
"Could you do a recursive elimination instead?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview