Amazon Web Services has n servers where the vulnerability score of the i-th server is vulnerability[i]. A client wants to deploy their application on a group of m contiguous servers. The vulnerability of a group is defined as the kth minimum vulnerability among the chosen servers.
Find the vulnerability of each possible group of m contiguous servers the client can choose.
Example
k = 2
m = 3
vulnerability = [1, 3, 2, 1]There are 2 contiguous groups of m = 3 servers: [1, 3, 2] and [3, 2, 1].
The 2nd lowest vulnerability in each group is 2.
Return the answers for each group, in order: [2, 2].
Function Description
Complete the function findKthMinimumVulnerability in the editor below.
findKthMinimumVulnerability has the following parameter(s):
int k: the order of the vulnerability to findint m: the number of servers in a groupint vulnerability[n]: the vulnerabilities of each server
Returns:
int[n - m + 1]: the ith element represents the kth minimum vulnerability among the vulnerabilities of the ith contiguous group.
This is a sliding-window order-statistics problem: for every contiguous subarray of length m, return the kth smallest value in that window. A naive sort for each window is too slow, so the intended solution uses a data structure that supports insertions, deletions, and kth-element queries efficiently, such as a balanced BST, two heaps with lazy deletion, or a Fenwick tree with coordinate compression. In the example, both windows [1, 3, 2] and [3, 2, 1] have 2 as their 2nd smallest value, so the result is [2, 2].
