AlgoViz
HomeBinary Search

Kth element of 2 sorted arrays

Medium

The median search, generalised

Problem

Given two sorted arrays a and b of size m and n respectively, find the kth element of the final merged sorted array.

In simple words

Binary-search how many to take from the first array so the k-th boundary lands correctly.

The idea

The median is the k-th element for a particular k, so the same partition search works for any k: split so that exactly k elements sit on the left, then the answer is the larger of the two left-hand boundary values.

The trick

  • Set the left-half size to k and search the same partition.
  • Clamp the search bounds so neither array is over-drawn.
  • O(log min(m, n)).
a[2,3,6,7,9]
b[1,4,8,10]

Step 1 of 11. Brute force: merge both sorted arrays, then read off the 5-th value. a [2,3,6,7,9], b [1,4,8,10].

1/11
Brute force
timeO(m+n)spaceO(m+n)

Merge then pick.

1const merged = [];2while (i < a.length || j < b.length) merged.push(takeSmaller());3return merged[k - 1];

Memory

last
—
a
[2,3,6,7,9]
b
[1,4,8,10]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5
Output:
6
Explanation:
Merged, the 5th smallest is 6.

Example 2

Input:
a = [1, 2], b = [3, 4], k = 3
Output:
3
Explanation:
The 3rd element overall is 3.

Example 3

Input:
a = [5], b = [2, 7], k = 1
Output:
2
Explanation:
Smallest overall is 2.

Constraints

  • 1 <= m, n <= 10^4
  • 1 <= k <= m+n

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.