Count runs with at most k losing days

Question

Given a series of daily returns and a budget k, count how many contiguous runs contain at most k losing days (returns below zero). Every non-empty contiguous run counts if it satisfies the constraint.

returns = [1, -1, 2, -3], k = 1
-> 8

Return the number of contiguous runs with at most k negatives. Aim for $O(n)$ .

Accepted Answer

Slide a window that never holds more than k losing days. Extend the right edge; if the loser count exceeds k, shrink from the left until it is legal again. For each right position, every window ending there and starting anywhere from left to right is valid, so add right - left + 1 to the count. This "sum of valid window widths" tallies all qualifying runs in one pass. Tracing [1, -1, 2, -3] with k = 1: as the right edge advances, the valid-window widths are 1, 2, 3, 2, summing to 8. (The two runs containing both negatives, [-1, 2, -3] and the full array, are the only ones excluded from the 10…

Count runs with at most k losing days

Your answer

More Coding questions