Binary Subarrays With Sum - Video Solutions

Problem Overview: You are given a binary array nums and an integer goal. The task is to count how many contiguous subarrays have a sum exactly equal to goal. Because the array only contains 0 and 1, the total sum of any subarray equals the number of ones inside it.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Check every possible subarray. Start at each index, extend the subarray to the right, and maintain a running sum. Each time the sum equals goal, increment the count. This approach simply iterates through all start and end pairs, which leads to quadratic time. It works for small inputs but becomes slow when n grows because there are roughly n² / 2 subarrays to examine.

Approach 2: Prefix Sum with Hash Map (O(n) time, O(n) space)

This method uses the prefix sum idea combined with a hash table. Maintain a running prefix sum while iterating through the array. If the current prefix sum is curr, then any previous prefix sum equal to curr - goal indicates a valid subarray ending at the current index. Store counts of prefix sums in a hash map so lookups are constant time. For every element, update the running sum, check the map for curr - goal, and add that frequency to the answer. This approach handles all cases efficiently and works for any integer array, not just binary ones.

Approach 3: Sliding Window Using At-Most Trick (O(n) time, O(1) space)

Because the array contains only 0 and 1, you can use a sliding window technique. Instead of directly counting subarrays with sum equal to goal, compute atMost(goal) - atMost(goal - 1). The helper function counts subarrays with sum ≤ target using two pointers and a running window sum. Move the right pointer to expand the window and shrink from the left when the sum exceeds the limit. Each step adds the window length to the count, representing all valid subarrays ending at that index. The difference between the two counts gives exactly the number of subarrays with sum equal to goal.

Recommended for interviews: The prefix sum + hash map approach is the most common interview expectation because it demonstrates strong understanding of prefix sums and frequency maps. Mentioning the brute force approach first shows you understand the baseline solution. The sliding window trick is highly efficient for binary arrays and shows deeper insight into how array constraints can simplify the problem.