L9. Binary Subarrays With Sum | 2 Pointers and Sliding Window Playlist

This chapter explores how to efficiently compute the number of binary subarrays whose elements sum up to a specific target goal, moving from a suboptimal hashing approach to an optimal $O(N)$ time and $O(1)$ space Two Pointer and Sliding Window solution using a mathematical transformation trick.

1. Problem Statement and Status Quo

Given a binary array (containing only 0s and 1s) and an integer goal, our task is to compute the total number of contiguous subarrays where the sum of elements equals the goal.

Example Breakdown:

• Array: [1, 0, 1, 1, 0]
• Goal: 2
• Valid Subarrays:
  1. Index 0 to 2: [1, 0, 1] (Sum = 2)
  2. Index 1 to 3: [0, 1, 1] (Sum = 2)
  3. Index 0 to 3: [1, 0, 1, 1] (Sum = 3? No, invalid. Let's trace carefully.)
  • Let's re-verify the exact valid subarrays summing to 2:
    • [1, 0, 1] (indices 0..2)
    • [0, 1, 1] (indices 1..3)
    • [1, 1] (indices 2..3)
    • [1, 1, 0] (indices 2..4)
  • Total valid subarrays = 4.

2. Why the Hashing Approach Falls Short of Perfection

In general arrays containing both positive and negative numbers, the most optimal solution relies on Prefix Sums and Hashing (storing prefix sum frequencies in a hash map).

Note: While the hashing solution runs in $O(N)$ time and works for binary arrays, it incurs an $O(N)$ space complexity due to the hash map. Since our array is strictly binary (containing only 0s and 1s), can we achieve $O(1)$ auxiliary space by eliminating the hash map and using Two Pointers / Sliding Window?

3. The Dilemma of Direct Sliding Window (Sum == Goal)

When applying a traditional sliding window with L (Left) and R (Right) pointers to find subarrays where Sum == Goal, we hit a roadblock:

1. Expanding Right (R): We add elements to our window sum until the sum meets or exceeds the goal.
2. Shrinking Left (L): Once the sum exceeds the goal, we increment L to drop elements from the left.
3. The Core Obstacle (Zeros): Because the array contains 0s, shrinking or expanding doesn't behave monotonically with respect to an exact equality condition (==). Removing a 0 does not change the sum, whereas moving R past valid matches can cause us to prematurely miss valid subarrays or become trapped in a logical dilemma over whether to move L or R.

4. The Mathematical Shift: Sum <= Goal

Instead of solving directly for Sum == Goal, we can reframe the problem into a much friendlier sliding window format: Find the number of subarrays where Sum <= Goal.

Why is Sum <= Goal Easier?

When the sum is less than or equal to the goal, the window property is monotonic. If adding a new element keeps the sum $\le$ goal, then every possible subarray ending at R and starting anywhere from L to R is valid.

Length as Count Formula:

If our window spans from index L to R, the number of valid subarrays ending at R is given precisely by the window length:

5. Step-by-Step Evolution of the Sum <= Goal Algorithm

Let us trace how the window expands and counts subarrays for goal = 2 on [1, 0, 1, 1, 0]:

Step 1: R at index 0 ([1])
   - Sum = 1 (<= 2)
   - Valid subarrays ending here: [1] (Length = 0 - 0 + 1 = 1)
   - Total Count = 1

Step 2: R moves to index 1 ([1, 0])
   - Sum = 1 + 0 = 1 (<= 2)
   - Valid subarrays ending here: [1, 0], [0] (Length = 1 - 0 + 1 = 2)
   - Total Count = 1 + 2 = 3

Step 3: R moves to index 2 ([1, 0, 1])
   - Sum = 1 + 0 + 1 = 2 (<= 2)
   - Valid subarrays ending here: [1, 0, 1], [0, 1], [1] (Length = 3)
   - Total Count = 3 + 3 = 6

Step 4: R moves to index 3 ([1, 0, 1, 1])
   - Sum = 2 + 1 = 3 (> 2, Exceeds Goal!)
   - Shrink window from left (`L` increments until sum $\le$ goal):
     * Remove `1`, `L` shifts to index 1. Sum becomes `2`.
   - Valid subarrays ending here: `[0, 1, 1]`, `[1, 1]`, `[1]` (Length = 3 - 1 + 1 = 3)
   - Total Count = 6 + 3 = 9

6. The Master Formula: (Sum == Goal) = (Sum <= Goal) - (Sum <= Goal - 1)

Now that we have a robust function to calculate subarrays where Sum <= K, how do we get the exact count for Sum == Goal?

Using basic set theory / cumulative arithmetic:

• Subarrays with Sum $\le$ Goal: Counts all subarrays summing to $0, 1, 2, \dots, \text{Goal}$.
• Subarrays with Sum $\le$ Goal - 1: Counts all subarrays summing to $0, 1, 2, \dots, \text{Goal} - 1$.
• Difference: Exactly the subarrays summing strictly to Goal.

7. Edge Cases and Safeguards

• Goal is Negative (Goal < 0): Since our array only contains 0s and 1s, the minimum possible sum of any subarray is 0. It is impossible to have a subarray sum less than 0.
  • Safeguard: If goal < 0, our helper function immediately returns 0. This is crucial when we evaluate goal - 1 (e.g., if goal = 0, then goal - 1 = -1).

8. Complete Code Implementation (Java / Optimal Sliding Window)

Below is the clean, production-grade implementation combining the helper function and the mathematical subtraction:

class Solution {
    
    // Helper function to count subarrays with sum less than or equal to goal
    public int helper(int[] nums, int goal) {
        if (goal < 0) {
            return 0;
        }
        
        int l = 0, r = 0;
        int sum = 0;
        int count = 0;
        int n = nums.length;
        
        while (r < n) {
            sum += nums[r];
            
            // Shrink window from the left if sum exceeds goal
            while (sum > goal) {
                sum -= nums[l];
                l++;
            }
            
            // All subarrays ending at r and starting anywhere from l to r are valid
            count += (r - l + 1);
            r++;
        }
        
        return count;
    }
    
    // Main method computing exact binary subarrays with sum equal to goal
    public int numSubarraysWithSum(int[] nums, int goal) {
        return helper(nums, goal) - helper(nums, goal - 1);
    }
}

9. Complexity Analysis

Summary and Key Takeaways

• Problem Adaptation: Direct sliding window fails on exact equality (Sum == Goal) with binary arrays containing zeros due to lack of monotonicity.
• Monotonic Transformation: Solving for Sum <= Goal allows us to leverage window length (R - L + 1) for instant counting.
• The Core Equation: Exact equality is achieved via subtraction: Count(Sum == Goal) = Count(Sum <= Goal) - Count(Sum <= Goal - 1).
• Zero-Sum Safety: Always check if goal < 0 to prevent invalid states when evaluating goal - 1.
• Space Optimization: By switching from a Prefix Sum Hash Map to Two Pointers, we successfully reduced space complexity from $O(N)$ to $O(1)$ while maintaining optimal $O(N)$ time.