DAY 30 - Binary Subarrays With Sum

Hey Guys! Nayan here and this is the 30th day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here. I may be incorrect at many times and might be following a bad practice. Feedback is highly appreciated.

Question: Binary Subarrays With Sum

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

A subarray is a contiguous part of the array.

Example:

• Input: nums = [1,0,1,0,1], goal = 2
• Output: 4
• Explanation: The 4 subarrays are bolded and underlined below:
• [1,0,1,0,1]
• [1,0,1,0,1]
• [1,0,1,0,1]
• [1,0,1,0,1]

• Input: nums = [0,0,0,0,0], goal = 0
• Output: 15

Intuition:

I don't think we need to break down the question here, Since the question is pretty straight forward.
Let's head to observation and thought process.
We need to calculate the number of subarrays with binary sum K.
We can just calculate all subarrays and their sum and count with sum K.
But that will be a naïve thing to do and It will take so much time.
Let's try to think something better.
Let's recognize the pattern: We are given a goal to achieve, we must move in subarrays only, hence we have been given a window. We can't pick elements individually.

• Window + Goal + Condition == Sliding Window Problem.

Now that we have recognized it's a sliding window problem, let's see what will happen if we will calculate it using traditional sliding window without any modifications.

Approach: Sliding Window(Without Modification)

• We will declare two pointers, one sum and so on. We will move the window to the right. If we get our target == sum, we can add one to our answer. We can continue till our sum is greater than our target.
• Then we will move our window from it's left anchor up ahead and decrease sum accordingly and update right as well , as we will have to recalculate the window sum.
• But this will take O(N^2) complexity in the worst case.
• So we come up with a better approach.

Approach: Sliding Window with Modification

• Suppose there is an array which contains only numbers 0 , 1 and 2.
• Let's say if we want to calculate the no of 2s in our array , we can simply go through the array and count 2's.
• Let's look at it another way. We know the size of the array.
• If we can figure out how many 0's and 1's are there and we subtract it from total size, we also get no of 2's.
• We are going to do exactly that here. We are going to calculate subarrays which meet our at most goal. If we subtract that from our atmost(goal - 1). We will get the answer.

Algorithm:

• Create a function atMost with same parameters as original function.
• Initialize two pointers left and right as 0.
• Initialize a variable answer which stores our result and one variable sum which calculate sum as we go along.
• Create a for loop for right = 0 till right is less than size of array and increment sum with the value at index right.
• We check if we have crossed our goal and if we have, we just increment our left pointer and decrease our sum accordingly.
• Return right - left + 1.

Code:

int atMost(vector<int>& nums, int goal){
        int left = 0;
        int right = 0;
        int ans = 0;
        int sum = 0;
        for(right = 0; right < nums.size(); right++){
            sum += nums[right];
        while(left <=right && sum > goal){
            sum -= nums[left];
            left++;
        }
        ans += right - left + 1;
        }
        return ans;

    }
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return atMost(nums,goal) - atMost(nums, goal-1);

    }

Complexity Analysis:

Time Complexity: O(N)
Space Complexity: O(1). where N is the size of nums.