Sprint intervals

A running coach builds interval sessions out of a fixed playlist. Each block of the session must contain a set number of fast tracks — no more, no fewer.

The problem

The playlist is a list of tempos in beats per minute, in play order. A track is a push track when its tempo is 160 BPM or more; anything slower is a recovery track. A block is a contiguous run of tracks, and blocks starting or ending at different tracks are different blocks even if they sound the same.

Count the blocks holding exactly k push tracks. Note that k may be 0, which asks for the blocks with no push track at all.

Input. bpm — a list of integer tempos, possibly empty. k — a non-negative integer.

Output. The number of contiguous blocks containing exactly k push tracks.

Example.

bpm = [150, 168, 172, 145, 160], k = 2   ->  5

Tracks 1, 2 and 4 are push tracks. The five blocks are 0-2, 0-3, 1-2, 1-3 and 2-4. Note that 160 counts as a push track — treating the threshold as strictly greater than 160 gives 6 here.

A second example, with no push tracks at all:

bpm = [140, 150, 130], k = 0   ->  6

Every one of the six blocks qualifies, including the three single-track ones. An answer of 9 means empty blocks are being counted.

Constraints.

• 0 <= len(bpm) <= 10^5
• 40 <= bpm[i] <= 220
• 0 <= k <= 10^5

Hints

Approach

Brute force

Take every start, extend to every end, and count push tracks as you go. That is n * (n + 1) / 2 blocks — 5 * 10^9 on a full playlist — and each one recounts tracks the previous block already counted.

The insight

A block holds exactly k push tracks when its two ends' running totals differ by exactly k, so counting blocks becomes counting earlier prefixes with the right total.

The running total never falls as you walk forward, and it rises by exactly one per push track, so the count inside a block is a plain subtraction. Keeping a tally of how many prefixes have ended on each total turns the search for a matching start into a single dictionary lookup. The empty prefix, with a total of 0, has to be in the tally from the beginning — otherwise no block starting at track 0 is ever found.

Algorithm

1. Start a tally with 0 -> 1, a running total of 0 and an answer of 0.
2. For each track, add 1 to the running total if its tempo is at least 160.
3. Add tally[running - k], treating a missing key as 0, to the answer.
4. Increment tally[running].
5. Return the answer.

Complexity

Time O(n) — one pass, with one lookup and one insert per track. Space O(n) for the tally, which holds one key per distinct running total.

Solution

"""Sprint intervals — count blocks with exactly k push tracks via prefix counts."""

PUSH_BPM = 160


def solve(bpm, k):
    # seen[c] = how many prefixes ended with exactly c push tracks. The empty
    # prefix counts once, which is what lets a block start at track 0.
    seen = {0: 1}
    running = 0
    blocks = 0
    for tempo in bpm:
        if tempo >= PUSH_BPM:
            running += 1
        # Look up before storing, so the current prefix never pairs with itself.
        blocks += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return blocks

TESTS = [
    (([150, 168, 172, 145, 160], 2), 5),
    (([165, 120, 170, 118, 155, 161], 2), 5),
    (([140, 150, 130], 0), 6),
    (([180, 180], 1), 2),
    (([100], 1), 0),
    (([], 0), 0),
]

Pitfalls

• Forgetting the 0 -> 1 seed. Every block that starts at track 0 goes missing; the first example drops from 5 to 3.
• Incrementing the tally before the lookup. With k = 0 the current prefix matches itself, which counts a zero-length block at every step: the second example returns 9 instead of 6.
• Using > for the threshold. A 160 BPM track is a push track by the definition given, and treating it as recovery turns the first example into 6.
• Reaching for the at-most-k subtraction. It works, but each half needs a window over a monotone quantity, and the prefix tally already answers exactly k in one pass.

Variants

• Exactly k stops — exactly k again, but over distinct values, where no prefix count exists and two at-most windows are subtracted instead.