DSA interview question

Binary Subarrays With Sum

Hard · Algorithms · Topics: sliding window, prefix sum, array

The problem

An ad-tracking system logs each second as 1 (a click happened) or 0 (no click), and analysts want the number of contiguous time ranges with exactly goal clicks. "Exactly" is awkward for a sliding window, but "at most" is easy: since values are non-negative, the window sum only grows as it widens. So compute atMost(goal) − atMost(goal − 1), where atMost(g) counts subarrays with sum ≤ g by adding, for each right end, the number of valid starts.

Example: [1, 0, 1, 0, 1], goal = 2 → 4.

Function signature

long long numSubarraysWithSum(const vector<int>& nums, int goal);  // nums[i] is 0 or 1

Test cases

Input `(nums, goal)`	Output	Explanation
`([1, 0, 1, 0, 1], 2)`	`4`	[1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1]
`([0, 0, 0, 0, 0], 0)`	`15`	Every subarray: 5 · 6 / 2
`([1, 1, 1], 2)`	`2`
`([0, 1, 0], 1)`	`4`
`([1, 0, 1], 5)`	`0`

(Confirm: subarrays are non-empty and contiguous; values are 0/1; the count can be about n²/2, so use 64-bit.)

How interviewers phrase it

"Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum of goal" (LeetCode 930).

Clarifying questions to ask

Are values only 0 and 1? (Yes, non-negative matters for the window trick.)
Can goal be 0? (Yes: count subarrays of zeros.)
How large is n? (Up to 3·10⁴, and the answer can exceed 32 bits in general.)

Follow-ups to expect

"Why not a direct 'exactly goal' window?"
"Why does atMost work?"
"Alternative?"
"What's atMost(−1)?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview