Find Kth Minimum Vulnerability
Amazon● MediumFULLTIMEOAProblem statement
A service has n servers in a row, where vulnerability[i] is the vulnerability score of the server at index i.
A client chooses a contiguous group of exactly m servers. The vulnerability of that group is its kth minimum value: sort the group's scores in non-decreasing order and take the value at one-based position k. Repeated scores occupy separate positions.
Find this vulnerability for every possible group of m contiguous servers. Return the values in left-to-right window order.
Function
findKthMinimumVulnerability(k: int, m: int, vulnerability: int[]) → int[]Examples
Example 1
k = 2m = 3vulnerability = [1, 3, 2, 1]return = [2, 2]The two length-3 groups are [1, 3, 2] and [3, 2, 1]. Each group sorts to [1, 2, 3], whose second minimum is 2. Therefore, return [2, 2].
Example 2
k = 3m = 4vulnerability = [4, 2, 3, 1, 1]return = [3, 2]The groups are [4, 2, 3, 1] and [2, 3, 1, 1]. They sort to [1, 2, 3, 4] and [1, 1, 2, 3], whose third minimum values are 3 and 2. Therefore, return [3, 2].
Constraints
1 ≤ k ≤ m ≤ n ≤ 3 × 1051 ≤ vulnerability[i] ≤ 109