Binary Subarrays With Sum
Medium · Sliding Window · Array · Hash Table · Sliding Window · Prefix Sum
Problem
Given a binary array nums (every value is 0 or 1) and an integer goal, return the number of non-empty contiguous subarrays whose sum equals goal: the subarrays that contain exactly goal ones.
A window with exactly goal ones can still grow by zeros on either side, so a single window does not settle "exactly". The trick is to count something a window can settle, at most goal ones, twice.
Examples
Input: nums = [0,1,0,1,1], goal = 2 Output: 4
The subarrays are [0,1,0,1], [1,0,1], [0,1,1] and [1,1]: [0,1,0,1] and [1,0,1] share the same two ones, with or without the zero before them.
Input: nums = [0,0,0], goal = 0 Output: 6
All 6 subarrays (three of length 1, two of length 2, one of length 3) contain no ones.
Input: nums = [1,0,1], goal = 3 Output: 0
The array holds only two ones, so no subarray reaches 3.
Constraints
- 1 <= len(nums) <= 3 · 10^4
- nums[i] is 0 or 1
- 0 <= goal <= len(nums)
Approaches
- Every start, extend until the sum passes goal — time O(n²), space O(1)
Follow-up
A prefix-sum hash map (count earlier prefixes equal to prefix − goal) also solves it in O(n), and it keeps working when values can be negative, where the window does not. Which approach would you pick for "subarrays with exactly k odd numbers"?
Related problems
Start free on Cariara · Coding problems · System design studio
