Count windows and maintain frequencies
Count all valid starts, or store occurrences when a sum is not the right summary.
Understand the idea
After repairing an inclusive nonnegative-sum window [left, right] to sum ≤ K, every suffix starting between left and right is also valid. Add right − left + 1 to count all valid windows ending at right. For constraints such as at most k distinct values, maintain a frequency table and a distinct counter instead of a sum.
Trace a small example
For [1, 2, 1] with K = 3, the per-right counts are 1, 2, 2, totaling 5. For [a, b, a], removing the first a must not decrease the distinct counter: another a is still present. A count reaches zero only when the value leaves the window entirely.
Conditions and cost
Use a wide answer: an array can have n(n + 1)/2 subarrays. For nonnegative integer sums, exact(K) = atMost(K) − atMost(K − 1), with atMost(negative) = 0. Frequency-map operations add their own cost.
Frequency array
The value becomes an index. Each arrival increases freq[value] by one. This domain has ten possible values.
Input values
freq[value] — indices are values
The frequencies add up to 6, the number of input values.
Guided simulation · Change the inputs to test your understanding.
When should removing a value reduce the distinct counter?
Turn the idea into code
How many subarrays of [0, 0, 1] have sum exactly zero?
Give me a hint
Subtract atMost(−1) from atMost(0), or enumerate zero-only windows.
Show the explained solution
There are 3: each individual zero and the pair of zeros. Counting only one match per right endpoint would miss one.
Your notes
Mark complete when you can explain it yourself.