Workspace

Problem workspace

3 day streakD

Binary Subarrays with Sum

MediumSliding WindowCounting windows

The challenge

Count nonempty contiguous subarrays of a binary array whose sum equals goal.

Every value is 0 or 1; goal ≥ 0. Empty input returns 0.

Example

[1, 0, 1, 0, 1], goal = 2 → 4; [0, 0, 0], goal = 0 → 6.

Use the walkthrough below to inspect the input and each state change.

See Exact binary sum, step by step

Expand, shrink, and inspect the window state.

5 elements · zero-based indicestarget = 2
Sliding window over 5 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -11001120314
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 29

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

Input: [1,0,1,0,1] · target = 2

Current window is empty.

Put it into code

Nonnegative values support an at-most sum window. Subtract counts for goal and goal − 1 to include every valid zero-prefixed or zero-suffixed subarray.

Indices are zero-based. C++ uses C++17 or later.

def binary_subarrays_sum(nums, goal):
    def at_most(budget):
        if budget < 0:
            return 0
        left = total = window_sum = 0
        for right, value in enumerate(nums):
            window_sum += value
            while window_sum > budget:
                window_sum -= nums[left]
                left += 1
            total += right - left + 1
        return total
    return at_most(goal) - at_most(goal - 1)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap