Domain 2MediumMEDIUM

Binary Subarrays With Sum

Count subarrays with sum S using prefix sums and a hash map to achieve O(N) time complexity.

Domain: medium•Updated: 2026-09-04
#prefix_sum#hash_map#$O(N)$#$O(N)$

Problem Breakdown

We are given a binary array A containing only 0s and 1s, along with an integer target sum S. The goal is to count the number of contiguous subarrays (non-empty) where the elements add up exactly to S.

Inputs:

  • An array A consisting of integers {0, 1}.
  • A non-negative integer S.

Outputs:

  • An integer representing the total count of valid subarrays.

Constraints & Edge Cases:

  • Array length can be up to 30,000. This is a critical constraint; an O(N2)O(N^2) solution (roughly 900 million operations) will likely time out on platforms like LeetCode or FAANG interviews. We need something closer to linear time complexity.
  • S can range from 0 up to the length of the array.
  • If S = 0, we are looking for subarrays consisting entirely of zeros (since elements are non-negative). This is a tricky case because standard sliding windows often assume strictly increasing sums, but here adding a zero doesn’t change the sum.
  • Empty input: The loop won’t execute, returning 0 correctly.

Intuition

A naive brute-force approach would iterate through every possible start index i and end index j, calculating the subarray sum for each pair. This results in O(N2)O(N^2) time complexity because we might re-sum elements repeatedly or check sums inefficiently inside nested loops. Given N=30,000, this is too slow.

To optimize, we can leverage Prefix Sums. A key property of subarrays is that the sum from index i to j equals prefix_sum[j] - prefix_sum[i-1]. We want:

current_prefix_sum - previous_prefix_sum = S
previous_prefix_sum = current_prefix_sum - S

This transforms the problem into a lookup task. As we iterate through the array, maintaining a running sum of elements seen so far (current_prefix_sum), we can check how many times current_prefix_sum - S has occurred previously in our traversal history. If it has occurred kk times before, there are exactly kk valid subarrays ending at the current index with sum S.

We use a Hash Map (dictionary) to store the frequency of each prefix sum encountered so far. This allows us to perform lookups and updates in amortized O(1)O(1) time.

Approach

  1. Initialize State: Create a hash map (prefix_counts) initialized with {0: 1}. We start here because if our running sum equals S at the very beginning (without adding any elements yet), it implies we found a subarray starting from index 0 that sums to S, but technically an empty prefix has sum 0. This handles cases where the target is met immediately or when zeros are involved early on.
  2. Iterate: Loop through each number in A. Update our running current_sum by adding the current element (which is either 0 or 1).
  3. Lookup & Count: Check if (current_sum - S) exists as a key in our hash map. If it does, add its value to our total count variable. This represents all valid subarrays ending at the current index that sum up to S.
  4. Update Map: Increment the frequency of the current running sum in the hash map for future iterations.
  5. Return Result: After iterating through the entire array, return the accumulated count.

Complexity Analysis

  • Time Complexity: O(N)O(N). We traverse the input array exactly once. Dictionary operations (insertion and lookup) are amortized constant time on average. Thus, total work is proportional to N.
  • Space Complexity: O(N)O(N). In the worst case (e.g., an array of all 1s), every prefix sum from 0 to N will be distinct keys in our map. Therefore, we store at most N+1N+1 entries.

Solution

from typing import List

def numSubarraysWithSum(A: List[int], S: int) -> int:
    # Dictionary to store frequency of prefix sums encountered so far.
    # Initialize with {0: 1} because a sum of 0 exists before processing any elements 
    # (handles cases where the valid subarray starts at index 0).
    prefix_counts = {0: 1}
    
    current_sum = 0
    count = 0
    
    for num in A:
        current_sum += num
        
        # We need a previous_prefix such that: 
        # (current_sum - previous_prefix) == S
        # Therefore, we look up how many times (current_sum - S) has occurred.
        target_prev = current_sum - S
        
        if target_prev in prefix_counts:
            count += prefix_counts[target_prev]
            
        # Update the frequency of the current running sum for future subarrays starting later.
        prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
            
    return count

# Example usage matching problem description
if __name__ == "__main__":
    A = [1, 0, 1, 0, 1]
    S = 2
    print(numSubarraysWithSum(A, S)) # Output: 4
    
    # Edge case with zeros and target sum 0
    A_zeros = [0, 0, 0]
    S_zero = 0
    print(numSubarraysWithSum(A_zeros, S_zero)) # Output: 6 (subarrays of all zeros)

Edge Cases Handled

  • S = 0: The initialization {0: 1} ensures that if the running sum stays at 0 due to consecutive zeros or starting with a zero sequence, we correctly count subarrays consisting entirely of zeros. For example, in [0, 0], after first element sum is 0 (lookup finds initial 0), then second element sum is 0 (lookup finds previous two occurrences).
  • Empty Array: The loop simply does not execute, count remains 0, which is correct for an empty input.
  • No Matches Found: If no subarray sums to S, the lookup condition never triggers or returns valid counts, and we return 0 correctly.
  • Large Input Size (N=30,000N=30,000): The O(N)O(N) approach ensures execution completes well within time limits compared to an O(N2)O(N^2) brute force solution which would exceed typical operation thresholds (approx 1 second limit).