Binary Subarrays WIth Sum

XXX. Binary Subarrays with Sum

Array

Sliding Window

Prefix Sum

Problem Statement:

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal.

• Array contains only 0s and 1s
• Find subarrays with exact sum
• Subarrays can overlap

Algorithm:

1. **Key Insight**:
   • Count(sum = k) = Count(sum ≤ k) - Count(sum ≤ k-1)
   • Reduces exact sum to "at most" sum problem
   • Use sliding window for "at most" calculations
2. **Sliding Window**:
   • Maintain window with sum ≤ target
   • Count valid subarrays for each window
   • Use difference of counts for exact sum

Complexity:

Time Complexity: O(n), where n is array length
Space Complexity: O(1)

Implementation:

Java Solution:

public int numSubarraysWithSum(int[] A, int S) {
    return atMost(A, S) - atMost(A, S - 1);    // Difference gives exact count
}

private int atMost(int[] A, int S) {
    if (S < 0) return 0;                       // Handle negative target
    int res = 0, i = 0, preSum = 0;
    
    for (int j = 0; j < A.length; j++) {
        preSum += A[j];                        // Add current element
        while (preSum > S)                     // Shrink window if sum too large
            preSum -= A[i++];
        res += j - i + 1;                      // Count subarrays ending at j
    }
    return res;
}
                

Python Solution:

def numSubarraysWithSum(self, A: List[int], S: int) -> int:
    def atMost(S: int) -> int:
        if S < 0: return 0                     # Handle negative target
        res = i = pre_sum = 0
        
        for j in range(len(A)):
            pre_sum += A[j]                    # Add current element
            while pre_sum > S:                 # Shrink window if sum too large
                pre_sum -= A[i]
                i += 1
            res += j - i + 1                   # Count subarrays ending at j
        return res
    
    return atMost(S) - atMost(S - 1)          # Difference gives exact count
                

C++ Solution:

class Solution {
private:
    int atMost(vector& A, int S) {
        if (S < 0) return 0;                   // Handle negative target
        int res = 0, i = 0, preSum = 0;
        
        for (int j = 0; j < A.size(); j++) {
            preSum += A[j];                    // Add current element
            while (preSum > S)                 // Shrink window if sum too large
                preSum -= A[i++];
            res += j - i + 1;                  // Count subarrays ending at j
        }
        return res;
    }
    
public:
    int numSubarraysWithSum(vector& A, int S) {
        return atMost(A, S) - atMost(A, S - 1);  // Difference gives exact count
    }
};
                

Explanation:

• **Mathematical Insight**:
  • Exact count can be derived from "at most" counts
  • Difference eliminates subarrays with smaller sums
  • Handles both zero and non-zero targets
• **Window Management**:
  • Grow window by adding elements
  • Shrink when sum exceeds target
  • Count all valid subarrays for current end point
• **Counting Logic**:
  • j-i+1 counts subarrays ending at j
  • Each window position contributes multiple subarrays
  • Accumulate counts for all valid windows