All problems

Error Burst Users

Medium · sliding window

A website keeps a log of the errors its visitors run into. Entry i says that the visitor named users[i] hit an error at second times[i]. The entries are in no particular order, and one visitor can hit several errors in the same second.

A visitor is flagged if some k of their errors happened close together: the latest of those k errors is less than window seconds after the earliest one. In other words, there are k errors by that visitor with times t1 <= t2 <= ... <= tk and tk - t1 < window. Errors in the same second all count.

Return the names of all flagged visitors, each name once, sorted alphabetically (ordinary a to z order, so "ab" comes before "abc", which comes before "b"). Return an empty list if nobody is flagged.

Examples

Example 1

Input: users = ["bo", "al", "bo", "bo", "al"], times = [5, 1, 3, 4, 100], k = 3, window = 4

Output: ["bo"]

"bo" has errors at seconds 3, 4 and 5, which fit in a stretch of 2 seconds. "al" has only two errors, 99 seconds apart.

Example 2

Input: users = ["x", "x", "x"], times = [0, 10, 20], k = 2, window = 10

Output: []

The closest pair of errors is exactly 10 seconds apart, which is not less than the window of 10.

Example 3

Input: users = ["zed", "amy", "zed", "amy", "kim"], times = [7, 7, 7, 8, 7], k = 2, window = 1

Output: ["zed"]

"zed" has two errors in second 7. "amy" has errors at seconds 7 and 8, which are 1 second apart, not less than 1.

Constraints