FastPrep
Problem · Array

Fixed-K Kth Largest Stream

Learn this problem
● MediumAmazon Web Services logoAmazon Web ServicesNEW GRADONSITE INTERVIEW

Problem statement

You are given a fixed rank k, a non-empty initial catalog of integer values, and a finite sequence of values that arrive afterward.

After each arriving value is added to the catalog, report the kth largest value among all values seen so far. Duplicate values occupy separate positions in the ranking.

Return one result per arriving value. Keep only the information needed to answer the fixed-rank queries; storing the full sorted catalog is unnecessary.

Function

kthLargestAfterEachAdd(k: int, initialValues: int[], additions: int[]) → int[]

Examples

Example 1

k = 3initialValues = [4,5,8,2]additions = [3,5,10,9,4]return = [4,5,5,8,8]

After adding 3, the three largest values are 8, 5, 4. Later additions raise the third-largest value first to 5 and then to 8.

Example 2

k = 2initialValues = [5,5]additions = [5,4,6]return = [5,5,5]

The repeated value 5 fills multiple ranks. Even after 6 arrives, the second-largest value remains 5.

Example 3

k = 1initialValues = [-10]additions = [-5,-7]return = [-5,-5]

With k = 1, each result is the maximum value seen so far.

Constraints

  • 1 ≤ k ≤ initialValues.length ≤ 200000.
  • 1 ≤ additions.length ≤ 200000.
  • initialValues.length + additions.length ≤ 200000.
  • Every value is a signed 32-bit integer.

More Amazon Web Services problems

drafts saved locally
public int[] kthLargestAfterEachAdd(int k, int[] initialValues, int[] additions) {
    // Write your code here.
}
k3
initialValues[4,5,8,2]
additions[3,5,10,9,4]
expected[4,5,5,8,8]
checking account