Show problems as
Classic problem #930MediumArrayHash TableSliding WindowPrefix Sum

Binary Subarrays With Sum

Real-world version: Stretches With Exact Press Count
Tracked in this browser only
Read Binary Subarrays With Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A foot pedal on a press writes one entry per minute into a log. minutes[i] is 1 if the pedal was pressed during minute i and 0 if it was not.

A stretch is any run of one or more consecutive minutes from the log. Count the stretches that contain exactly goal presses. Two stretches are different when they start or end at different minutes, even when they hold the same entries.

Return that count.

Examples

Example 1

Input
minutes = [1, 1, 0, 1], goal = 2
Output
3

Writing a stretch as the minutes it covers, the qualifying ones are minutes 0-1, minutes 0-2 and minutes 1-3. Each of those holds two presses.

Example 2

Input
minutes = [0, 1, 0, 0, 1], goal = 1
Output
9

Six stretches hold only the press at minute 1: they start at minute 0 or 1 and end at minute 1, 2 or 3. Three more hold only the press at minute 4: they start at minute 2, 3 or 4 and end at minute 4.

Example 3

Input
minutes = [0, 0, 0], goal = 0
Output
6

The log has no presses at all, so every stretch qualifies: three of length one, two of length two and one of length three.

Example 4

Input
minutes = [1, 0, 1, 1], goal = 0
Output
1

The only stretch with no press is the single minute 1.

Example 5

Input
minutes = [1], goal = 0
Output
0

The one available stretch holds a press, so nothing qualifies.

Constraints

  • 1 <= minutes.length <= 3 * 10^4
  • minutes[i] is either 0 or 1.
  • 0 <= goal <= minutes.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_stretches(minutes: list[int], goal: int) -> int:
Java
public int countStretches(int[] minutes, int goal)

More on the same topics