Katkat
Back

Find the k-th Largest Value Across Two Sorted Arrays Without Fully Merging Them

GleanSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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

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

Input: a = [], b = [5, 8], k = 2
Output: 5

Example 3

Input: a = [2, 2, 2], b = [2], k = 4
Output: 2