Find the Kth Largest in Two Sorted Arrays
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two arrays sorted in ascending order and an integer `k`. Return the `k`th largest element among all elements from both arrays combined.
Count duplicates as separate elements.
Example:
- `a = [0, 1, 4, 5, 6, 7, 8, 10, 13]`
- `b = [1, 3, 4, 5, 8, 9, 11, 12]`
- `k = 3`
The combined elements in descending order begin with `13, 12, 11, 10, ...`, so the answer is `11`.
Quick Answer: This question evaluates proficiency with array manipulation and selection algorithms, specifically understanding order statistics and working with two sorted sequences.
You are given two arrays `a` and `b`, both sorted in ascending order, and an integer `k`. Return the `k`th largest element among all elements from both arrays combined.
Duplicates count as separate elements. For example, if the combined sorted order is `[9, 8, 8, 7]`, then the 2nd largest element is `8` and the 3rd largest element is also `8`.
Try to use the fact that the arrays are already sorted.
Constraints
- 0 <= len(a), len(b) <= 200000
- 1 <= k <= len(a) + len(b)
- -1000000000 <= a[i], b[i] <= 1000000000
- Both arrays are sorted in non-decreasing order
Examples
Input: ([0, 1, 4, 5, 6, 7, 8, 10, 13], [1, 3, 4, 5, 8, 9, 11, 12], 3)
Expected Output: 11
Explanation: The combined elements in descending order begin as [13, 12, 11, 10, ...], so the 3rd largest is 11.
Input: ([1, 2, 2, 2], [2, 2, 3], 4)
Expected Output: 2
Explanation: Combined descending order is [3, 2, 2, 2, 2, 2, 1]. The 4th largest element is 2.
Hints
- The largest remaining element must always be at the end of one of the two arrays.
- This is similar to the merge step of merge sort, but done from right to left and stopped after taking `k` elements.