Count subarrays within budget

Write codeMedium16 min

Your task

A marketing team logs its daily ad spend as non-negative integers. For budget planning they ask: how many contiguous runs of days (non-empty, any length) have total spend at most budget? Overlapping runs count separately. Since spend is never negative, growing a run can never decrease its total, use that. Example: spend = [2, 1, 3], budget = 3 gives 4: the runs are [2], [1], [3], and [2, 1].

Examples

count_affordable_runs(spend: list[int], budget: int) -> int
Example 1
Inputcount_affordable_runs([2, 1, 3], 3)
Output4