Katkat
Back

Find the K-th Smallest Value in Two Sorted Arrays

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given two nondecreasing integer arrays and a one-based integer k, return the k-th smallest value in their combined multiset. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

Find the K-th Smallest Value in Two Sorted Arrays

Given two nondecreasing integer arrays and a one-based integer k, return the k-th smallest value in their combined multiset. Duplicates count separately. Do not merge the full arrays.

Function Contract

Implement kth_smallest_two_sorted(a, b, k) -> int.

Constraints

  • 0 <= length of each array <= 200000, and at least one array is nonempty.
  • 1 <= k <= len(a) + len(b).
  • Values are integers between -10^9 and 10^9.
  • Expected extra space is O(1), with logarithmic search complexity in the shorter array.

Examples

a = [1, 3, 7], b = [2, 2, 9], k = 4
output = 3

a = [], b = [5], k = 1
output = 5

Hints

Hint 1

Exercise imbalanced inputs: Test an empty array, one array much shorter than the other, duplicate boundary values, and k at both extremes.

Hint 2

Honor the search bound: Merging until the k-th value can be correct but does not achieve logarithmic complexity in the shorter array.