Binary Subarrays with Sum - Count Subarrays where Sum is Equal to Goal

Introduction

Continuing with the 2-pointer SL sliding window playlist from the Strivers A2Z DS course.
Problem: Count Binary Subarrays with Sum Equal to Goal.
Recommended prerequisite: Video on counting subarrays where the sum equals K from arrays and hashing playlist.

Problem Statement

Given an array (binary array: only 1s and 0s) and an integer goal.
Task: Compute the number of subarrays where the sum is equal to the given goal.
Example: For array [1,0,1,1,0] and goal 2, the valid subarrays are [1,1,0], [1,1], [1,1], and [1,0,1] (total: 4).

Previous Solution Recap

Similar problem previously done with positive and negative integers.
Most optimal solution used hashing, with O(n) time and O(n) space complexities.
Goal: Optimize space complexity since the array has special conditions (binary array).

Optimizing the Solution

Parameters: Binary array, goal (sum to achieve).
Observation: Reduce external space (use of map data structure).
New Goal: Achieve O(n) time and O(1) space complexity.

Approach

Use Two-pointer or Sliding Window technique since no external data structure is preferred.
Problem involves counting subarrays, not finding the longest subarray.

Sliding Window Analysis

Example: Array [1,0,1,1,0], goal 2.
Pseudocode and Steps:
- Initialize pointers L and R at 0, and sum and count at 0.
- Iterate over the array; add elements to sum while moving R.
- If sum exceeds goal, move L to shrink the window until sum <= goal.
- Count all valid subarrays in each iteration.

Example Walkthrough

Initial State: sum = 0, count = 0
R at 0: sum = 1 (Valid subarray count = 1)
R at 1: sum = 1 (Valid subarray count = 2)
R at 2: sum = 2 (Valid subarray count = 3)
Move R to 3, shrink window by moving L to 1: sum = 2
Move R to 4, L to 2: sum = 2
Continue until R exceeds array bounds.

Complexity Analysis

Initial Sliding Window Function: O(n) time, O(1) space.

Optimization

Simplify problem to find subarrays where sum is ≤ goal, then subtract subarrays where sum is ≤ (goal-1).

Final Algorithm

Count subarrays where sum is ≤ goal.
Count subarrays where sum is ≤ (goal-1).
Subtract the second count from the first to get subarrays where sum is exactly goal.

Edge Cases

Handle special conditions where the goal might be less than zero.

Pseudocode

def count_subarrays_with_sum(nums, goal):
    def count_sub_arrays_with_sum_lte(nums, goal):
        L = 0
        current_sum = 0
        count = 0
        for R in range(len(nums)):
            current_sum += nums[R]
            while current_sum > goal:
                current_sum -= nums[L]
                L += 1
            count += R - L + 1
        return count
    if goal < 0:
        return 0
    return count_sub_arrays_with_sum_lte(nums, goal) - count_sub_arrays_with_sum_lte(nums, goal - 1)

Conclusion

Sliding window technique effectively reduces space complexity to O(1).
Final solution provides optimal O(n) time and O(1) space complexity.

Call to Action

Like, subscribe, and share the video if you found it helpful.
Stay tuned for more informative videos. Take care!