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
Aconsisting 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 solution (roughly 900 million operations) will likely time out on platforms like LeetCode or FAANG interviews. We need something closer to linear time complexity.
Scan 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 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 times before, there are exactly 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 time.
Approach
- Initialize State: Create a hash map (
prefix_counts) initialized with{0: 1}. We start here because if our running sum equalsSat 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. - Iterate: Loop through each number in
A. Update our runningcurrent_sumby adding the current element (which is either 0 or 1). - 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 toS. - Update Map: Increment the frequency of the current running sum in the hash map for future iterations.
- Return Result: After iterating through the entire array, return the accumulated count.
Complexity Analysis
- Time Complexity: . 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: . In the worst case (e.g., an array of all 1s), every prefix sum from
0toNwill be distinct keys in our map. Therefore, we store at most 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 at0due 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,
countremains 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 (): The approach ensures execution completes well within time limits compared to an brute force solution which would exceed typical operation thresholds (approx 1 second limit).