Quick 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.

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.

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. Rank 1 is the largest value in the combined collection, rank 2 the next largest, and so on. Duplicates count separately: a value that appears three times overall occupies three consecutive ranks. Either array may be empty, but not both. Do not modify the inputs. A solution that is linear in `k` is correct, but aim for a running time logarithmic in the array lengths. Return a single integer. Every input value and the answer lie in [-10^9, 10^9], so they fit in a signed 32-bit integer (no value exceeds 2^31 - 1). ### 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 ``` The combined values in descending order are 8, 5, so the second largest is 5. **Example 3** ```text Input: a = [2, 2, 2], b = [2], k = 4 Output: 2 ``` All four values are equal, so every rank holds 2.

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

Input: ([1, 5, 11, 20], [3, 11, 14], 3)

Expected Output: 11

Explanation: Source example 1: descending 20, 14, 11, 11, 5, 3, 1; the duplicate 11 from both arrays fills ranks 3 and 4.

Input: ([], [5, 8], 2)

Expected Output: 5

Explanation: Source example 2: a is empty; descending 8, 5, so rank 2 is 5.

Hints

  1. Rank k counted from the largest end is rank len(a) + len(b) - k + 1 counted from the smallest end; use whichever direction is easier to reason about.
  2. Both inputs are already sorted, so a single comparison between an element of a and an element of b can rule out many candidate positions at once instead of stepping through elements one by one.
  3. Before optimizing, check the edge cases: one array empty, k = 1, k = len(a) + len(b), and duplicates that straddle rank k.

Loading coding console...

Show the approach

Approach

Let n = len(a) + len(b) and t = n - k + 1; the k-th largest value is the t-th smallest. The t smallest elements of the combined collection can always be taken as a prefix a[0..i-1] together with a prefix b[0..j-1] where i + j = t, so the task reduces to finding the split i, which must satisfy max(0, t - len(b)) <= i <= min(t, len(a)). Binary-search i over that range: at a midpoint i with j = t - i, compare a[i] with b[j-1]. If a[i] < b[j-1], the split takes too few elements from a, so move right; otherwise move left. The test a[i] >= b[t-i-1] is monotone in i because a[i] never decreases and b[t-i-1] never increases as i grows, so the search ends at the smallest i that passes (or at the upper end of the range). At that i, b[j-1] <= a[i] whenever both exist (the test passed) and a[i-1] < b[j] whenever both exist (the test failed at i - 1), so every taken element is at most every untaken element and the t-th smallest is max(a[i-1], b[j-1]), skipping whichever prefix is empty. Duplicates need no special handling because only how many elements each prefix holds matters, not whether values are distinct. Edge cases: one empty array collapses the search range to a single split; k = 1 takes everything (t = n) and k = n takes a single element (t = 1). Only comparisons and index arithmetic are performed, so values in [-10^9, 10^9] never overflow a 32-bit integer. The inputs are only read, never modified.

Time complexity:
O(log(min(len(a), len(b))))
Space complexity:
O(1)