Windows With an Exact Alarm Count

Medium

Once a minute a sensor writes 1 to the log log if an alarm went off during that minute, and 0 otherwise. A window is a non-empty run of consecutive minutes in the log. Count the windows in which the alarm went off exactly alarms times.

Example 1

log=[0, 1, 0, 0, 1], alarms=1 → 9

The windows holding exactly one 1 are [0,1], [0,1,0], [0,1,0,0], [1], [1,0], [1,0,0] around the first alarm, and [0,0,1], [0,1], [1] around the second: 9 in total.

Example 2

log=[1, 1, 1], alarms=2 → 2

Only the first two minutes and the last two minutes give exactly two alarms.

Example 3

log=[1, 0, 1], alarms=0 → 1

Constraints

1 ≤ len(log) ≤ 3·10⁴
each log[i] is 0 or 1
0 ≤ alarms ≤ len(log)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Prefix Sum Sliding Window

Similar problems

Stretches With k Odd Numbers Medium Trim the Ends to a Target Medium A Stretch of a Looping Playlist Medium Shortest Stretch to the Goal Medium Longest Run with a Given Sum Medium

Input

log=[0, 1, 0, 0, 1], alarms=1

Expected

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