Frost Rank in a Sliding Window

Medium

A weather station logged daily temperatures temps. For every stretch of width consecutive days, find the "frost of rank rank": sort the stretch's temperatures in ascending order and take the rank-th one. If it is negative, that is the answer for the stretch; otherwise the answer is 0 (the stretch has fewer than rank frosty days). Return the answers for all stretches, starting with the first: len(temps) - width + 1 numbers in total.

Example 1

temps=[-4, 2, -7, -1, 0], width=3, rank=2 → [-4, -1, -1]

Windows: [-4, 2, -7], second coldest -4; [2, -7, -1], second coldest -1; [-7, -1, 0], second coldest -1.

Example 2

temps=[3, -2, 5, 6], width=2, rank=2 → [0, 0, 0]

No window has two frosty days, so every answer is 0.

Example 3

temps=[-9, -9, 4], width=1, rank=1 → [-9, -9, 0]

Constraints

1 ≤ len(temps) ≤ 10⁵
1 ≤ width ≤ len(temps)
1 ≤ rank ≤ width
-50 ≤ temps[i] ≤ 50

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Sliding Window

Similar problems

Two-Genre Stretch of a Playlist Medium Windows With an Exact Alarm Count Medium Stretches With k Odd Numbers Medium Two Separate Segments With a Given Sum Medium Trim the Ends to a Target Medium

Input

temps=[-4, 2, -7, -1, 0], width=3, rank=2

Expected

[-4, -1, -1]

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.