Find the K-th Smallest Value in Two Sorted Arrays
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# 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
```text
a = [1, 3, 7], b = [2, 2, 9], k = 4
output = 3
```
```text
a = [], b = [5], k = 1
output = 5
```
```hint Exercise imbalanced inputs
Test an empty array, one array much shorter than the other, duplicate boundary values, and k at both extremes.
```
```hint Honor the search bound
Merging until the k-th value can be correct but does not achieve logarithmic complexity in the shorter array.
```
Quick Answer: 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.
Given two nondecreasing integer arrays and one-based `k`, return the k-th smallest value in their combined multiset. Count duplicates separately and do not merge the full arrays. Search must be logarithmic in the shorter array with constant extra space.
Constraints
- 0 <= len(a), len(b) <= 200000, and at least one array is nonempty.
- Both arrays are nondecreasing and values range from -10^9 through 10^9.
- 1 <= k <= len(a) + len(b), with duplicates counted separately.
- Do not merge the arrays; use logarithmic search in the shorter array and constant extra space.
Examples
Input: ([], [5], 1)
Expected Output: 5
Explanation: An empty first array returns the only value from the second.
Input: ([5], [], 1)
Expected Output: 5
Explanation: An empty second array is handled symmetrically.
Hints
- Test either array empty, one array much shorter, and k at both one-based extremes.
- Include duplicates equal across the candidate partition boundary.
- Use negative values and both numeric limits in sorted order.