Find the k-th Largest Value Across Two Sorted Arrays Without Fully Merging Them
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two integer arrays `a` and `b`, each sorted in non-decreasing order, and an integer `k`. Return the `k`-th largest value in the combined collection of all elements of both arrays.
Duplicates count separately: a value that appears three times overall occupies three consecutive ranks. A solution that is linear in `k` is correct, but the interviewer expected a faster approach, so aim for a running time logarithmic in the array lengths.
### Function Signature
```python
def kth_largest(a: list[int], b: list[int], k: int) -> int:
```
### Rules
- Rank 1 is the largest value in the combined collection, rank 2 the next largest, and so on, with duplicates counted separately.
- Either array may be empty, but not both.
- Do not modify the inputs.
### Constraints
- `0 <= len(a), len(b) <= 100000` and `1 <= len(a) + len(b)`
- `1 <= k <= len(a) + len(b)`
- `-10^9 <= a[i], b[j] <= 10^9`
- Both arrays are sorted in non-decreasing order.
### Examples
**Example 1**
```text
Input: a = [1, 5, 11, 20], b = [3, 11, 14], k = 3
Output: 11
```
In descending order the combined values are 20, 14, 11, 11, 5, 3, 1. The third is 11, and so is the fourth.
**Example 2**
```text
Input: a = [], b = [5, 8], k = 2
Output: 5
```
**Example 3**
```text
Input: a = [2, 2, 2], b = [2], k = 4
Output: 2
```
Overview: Given two arrays sorted in non-decreasing order and an integer k, return the k-th largest value among all their elements, counting duplicates separately. Tests reasoning about ranks across two sorted sequences, careful handling of empty arrays and duplicates, and moving past a linear scan toward logarithmic time.