Stretches With Exactly G Lit Lamps
MediumSliding Window
Problem
A row of street lamps is given as bits, where 1 means the lamp is lit and 0 that it is off. An inspector wants to know how many contiguous stretches of lamps contain exactly `goal` lit lamps.
Return the number of non-empty subarrays of bits whose sum equals goal.
Example 1
- Input:
- bits = [0, 1, 1, 0, 1], goal = 2
- Output:
- 5
[0,1,1], [1,1], [0,1,1,0], [1,1,0] and [1,0,1] each contain two lit lamps.
Example 2
- Input:
- bits = [0, 0, 0], goal = 0
- Output:
- 6
Every one of the 6 subarrays has no lit lamp.
Constraints
- 1 ≤ bits.length ≤ 3·10^4
- bits[i] is 0 or 1
- 0 ≤ goal ≤ bits.length
Hint
Show the first hint
Counting windows with sum at most g is easy with a sliding window. Is 'exactly g' directly windowable?
Walkthrough
How to approach it
01Clarify before coding
- Can goal be 0? Yes: count the stretches made only of off lamps.
- Can goal exceed the number of lit lamps? Yes; the answer is then 0.
- Only 0s and 1s? Yes, which keeps window sums monotone.
02Brute force
For every start, extend to the right with a running sum and count the ends where it equals goal.
Cost: O(n²) time, about 4.5·10^8 steps for n = 3·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.