K-th element of two Arrays

You are given two integer arrays a and b, each sorted in non-decreasing order, and an integer k.

Imagine merging a and b into one combined sorted array. Return the element that would sit at the k-th position (1-indexed) of that merged array.

The merged array is a thought experiment — the best solutions never actually build it. k is guaranteed to be valid: 1 <= k <= a.size() + b.size().

Hints

· Stuck? Reveal one nudge at a time.

The combined sorted array is imaginary — you never have to build it. You are being asked for exactly one number: the k-th smallest value across both arrays.

Suppose you take cutA elements from the front of a. Exactly k - cutA must then come from the front of b. The whole problem is now a single unknown integer.

Binary search cutA over the smaller array. A split is correct precisely when the last element taken from each array is <= the first element left behind in the other — and the answer is the larger of the two last-taken elements.

Common doubts

1-indexed: k = 1 asks for the smallest element overall, and k = n + m asks for the largest. The reference solutions return merged[k - 1] in the brute force for exactly this reason.

Yes. That is why the border test uses <= rather than < — with strict inequality, a value present in both arrays can make every split look invalid and derail the binary search.

Then the correct cut sits at 0 or at the full length of an array. The -inf / +inf sentinels make those cuts test cleanly with no special-case branches.

Correctness holds either way, but searching the smaller array bounds the work at O(log (min(n, m))) and keeps cutB = k - cutA in range with the simple bounds max(0, k - m) and min(k, n).

Interview follow-ups

· What an interviewer asks next.

It is this problem in disguise: the median is the k-th element with k = (n + m + 1) / 2 (and for even totals, also k + 1, averaged). The same partition binary search solves it in O(log (min(n, m))).

The two-array partition trick does not extend cleanly. Use a min-heap of the M array fronts and pop k times — O(k log M) — or binary search on the value range, counting elements <= mid across all arrays with M binary searches per step.

Random access dies, so the partition search is out — but the two-pointer merge walk only ever looks at the current front of each stream, making it the right tool: O(k) time, O(1) memory, purely sequential reads.

Fun facts

Set k to the middle of the combined length and this problem becomes Median of Two Sorted Arrays — one of the most feared interview classics falls out of this one as a special case.
The lazy merge walk in the better solution is the heart of external sorting and of how search engines merge ranked result lists — k-way merging with early stopping shows up everywhere two ordered sources meet.

Asked at

AmazonMicrosoftGoogleFlipkartOracle

Frequently Sometimes Occasionally

Example 1

Input: a[] = [2, 3, 6, 7, 9], b[] = [1, 4, 8, 10], k = 5
Output: 6
The combined sorted array is [1, 2, 3, 4, 6, 7, 8, 9, 10]. Its 5th element is 6.

Example 2

Input: a[] = [1, 4, 8, 10, 12], b[] = [5, 7, 11, 15, 17], k = 6
Output: 10
The combined sorted array is [1, 4, 5, 7, 8, 10, 11, 12, 15, 17]. Its 6th element is 10.

Constraints

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

Two arrays, already sorted — and one question: who is the k-th smallest overall? The naive answer merges everything; the beautiful answer cuts both arrays in one binary search and never merges at all. This is the general form of Median of Two Sorted Arrays, and the partition trick you learn here unlocks that classic too.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search on an index range. We binary-search over how many elements to take from one array, not over values — the search space is a range of cut positions.

The merge step of merge sort. Two front pointers walking two sorted arrays in order — the better solution is exactly this walk, stopped early.

Sentinel values. When a cut sits at the very start or end of an array, we substitute -inf / +inf so the border comparisons need no special cases.

Understand the problem

Restated: a and b are sorted. If they were merged into one sorted array, return the element at position k (1-indexed). We must do it faster than merging.

Worked example — a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5

merged (never actually built):
pos:   1   2   3   4   5   6   7   8   9
val:   1   2   3   4   6   7   8   9  10
                       ^
                 k-th element = 6

Clarifying questions

Asking two or three sharp questions before coding signals that you design for the real input, not the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are both arrays guaranteed to be sorted, and in which direction?”

Yes, non-decreasing. Every solution here leans on that; if they were unsorted you would be forced into an O((n+m) log (n+m)) sort.

“Is k always within range, and is it 1-indexed?”

Yes — 1 <= k <= n + m, and k = 1 means the smallest element. Off-by-one here is the classic silent bug.

Edge cases

“Can the arrays share duplicate values?”

Yes. Ties must be broken consistently (<= in the border test), otherwise the binary search can oscillate or return a wrong border.

“What if every element of one array is smaller than every element of the other?”

Then the optimal cut sits at 0 or at the full length of an array — the -inf / +inf sentinels exist exactly for this.

Constraints and scale

“How large can the arrays get?”

Up to 10^6 each, so k can be up to 2 * 10^6. An O(k) merge-walk passes, but the interviewer is fishing for O(log (min(n, m))).

The ideal opening — say it like this

Before I start, I have a few clarifying questions.

First — both arrays are sorted non-decreasing, and k is 1-indexed and always valid, correct?

Can values repeat across the two arrays? I want to make sure my tie-breaking is consistent.

And since sizes reach a million each, I will aim for a logarithmic partition-based solution rather than merging.

Key observations

1Aha

You are choosing a split, not searching a value

The first k elements of the merged array must be some cutA elements from the front of a plus exactly k - cutA from the front of b. So the whole problem collapses to one unknown integer: cutA.

a:  [ x  x  x | . . . ]     take cutA from a
b:  [ y  y | . . . . ]      take k - cutA from b
      \____ these k values are the merged prefix ____/

2Aha

A split is valid when the borders interlock

A guess for cutA is correct exactly when nothing left behind should have gone first: leftA <= rightB and leftB <= rightA, where leftA / leftB are the last elements taken and rightA / rightB the first elements left. When that holds, the k-th element is max(leftA, leftB) — the largest thing inside the prefix.

3Aha

Validity is monotonic, so binary search wins

If leftA > rightB, you took too many from a — shrink cutA. Otherwise you took too few — grow it. One comparison always tells you which way to move, so binary search over cutA in [max(0, k - m), min(k, n)] finds the valid split in O(log (min(n, m))) steps.

Brute force vs optimal

	Merge and sort	Two pointers	Binary search
Time	O((n+m) log (n+m))	O(k)	O(log (min(n, m)))
Space	O(n+m)	O(1)	O(1)

Full, runnable code for all three lives in the Approaches selector below.

Summary

Key takeaway

Selection in sorted data is a partition-counting binary search: guess how many of the first k come from one array, test the guess with one border comparison, and halve the range. The same interlocking-borders test solves Median of Two Sorted Arrays.

if len(a) > len(b): swap a, b
lo, hi = max(0, k - m), min(k, n)
while lo <= hi:
    cutA = (lo + hi) / 2 ; cutB = k - cutA
    leftA, rightA, leftB, rightB  (with -inf / +inf sentinels)
    if leftA <= rightB and leftB <= rightA: return max(leftA, leftB)
    if leftA > rightB: hi = cutA - 1   else: lo = cutA + 1