Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1
3.1.
Code
3.2.
Complexity Analysis
4.
Approach 2
4.1.
Code
4.2.
Complexity Analysis
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Binary Subarrays with Sum

Author Husen Kagdi
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Ashish and Aditya are preparing for the upcoming placement drive on their campus. They are practising coding problems from Leetcode. One day they found an interesting problem, namely, Binary Subarrays with sum. They are not sure how to solve it. So let us discuss the problem statement and various approaches to solve the problem.

Must Recommended Topic, Hash Function in Data Structure.

Problem Statement

Given a binary array, that is, an array containing only ones and zeros and an integer goal, find the number of subarrays with the sum equal to the goal. Recall that a subarray is a contiguous part of an array.

Example:

Array = [1, 0, 1, 0, 1], goal = 2.

The subarrays with the sum equal to the goal are:

[1, 0, 1, 0, 1]
[1, 0, 1, 0, 1]
[1, 0, 1, 0, 1]
[1, 0, 1, 0, 1]

Thus the output is 4.

Output: 4.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

This is a brute force approach. In this approach, we find every subarray and calculate its sum. If the sum is equal to the goal, we increment the answer. We can find all the subarrays using two nested loops. Have a look at the code given below.

Code

#include<iostream>
#include<vector>
using namespace std;
int helper(vector<int>& nums, int goal) {
  int l=nums.size();
  int ans=0;
  int k=0;
  
  // Counting number of zeros.
  for(int i=0;i<l;i++){
      if(nums[i]==0) k++;
  }
  
  // If all the elements of the array are 0, and the goal is greater than zero
  // then we cannot create a subarray with that sum.
  if(k==l && goal>0) return 0;

  // If all the elements of the array are 0, and the goal is equal to zero
  // then return all possible subarrays of the array.
  if(k==l && goal==0) return (l*(l+1))/2;
  
  for(int i=1;i<=l;i++){
      int sum=0;

      // Calculating sum till ith index.
      for(int j=0;j<i;j++){
          sum+=nums[j];
      }
      
      // If the sum  is equal to the goal, increment answer.
      if(sum==goal) ans++;
      
      for(int j=i;j<l;j++){
          // Calculating sum of subarray between ith and jth index.
          sum=sum-nums[j-i]+nums[j];

          if(sum==goal) ans++;
      }
  }
  return ans;
}
int main(){
  int N;
  cin>>N;
  vector<int> v(N);
  for(int i=0; i<N; i++){
      cin>>v[i];
  }
  int goal;
  cin>>goal;
  cout<<helper(v, goal);
  return 0;
}

Input

4
1 0 1 0 1
2

Output

4

Complexity Analysis

Time Complexity

O(N * N), where N is the size of the array.

 

We find all the subarrays of the array with two nested loops. Thus it is O(N * N) time. 

Space Complexity

O(1)

 

We are only declaring a few variables. Thus it takes constant space.

You can also read about the Longest Consecutive Sequence.

Approach 2

Let's count the number of I's with the subarray [I, J] equal to S for each J. These I's form an interval [I_LOW, I_HIGH], and each of these I_LOW, I_HIGH is rising in relation to J. As a result, we can choose a "two-pointer" method.

Algorithm

Let's keep four variables for each J (in increasing order):

sum lo: the sum of [I_LOW, J] subarrays

sum hi: the sum of [I_HIGH, J] subarrays

sum lo = S because I_LOW is the lowest I.

sum hi = S because I_HIGH is the greatest I.

The number of subarrays ending in j is then I_HIGH - I_LOW + 1 (assuming sum lo == S). For example, when J = 5, we want I_LOW = 1 and I_HIGH = 3 with A = [1,0,0,1,0,1] and S = 2.

Code

#include<iostream>
#include<vector>
using namespace std;
int helper(vector<int>& A, int goal) {
  int iLow = 0, iHigh = 0;
  int sumLow = 0, sumHigh = 0;
  int ans = 0;

  for (int j = 0; j < A.size(); ++j) {
      // While sumLow is too big, iLow++
      sumLow += A[j];

      while (iLow < j && sumLow > goal)
          sumLow -= A[iLo++];

      // While sumHigh is too big, or equal and we can move, iHigh++
      sumHigh += A[j];
      while (iHigh < j && (sumHigh > goal || sumHigh == S && A[iHigh] == 0))
          sumHigh -= A[iHigh++];

      if (sumLow == goal)
          ans += iHigh - iLow + 1;
      }

      return ans;
}
int main(){
  int N;
  cin>>N;
  vector<int> v(N);
  for(int i=0; i<N; i++){
      cin>>v[i];
  }
  int goal;
  cin>>goal;
  cout<<helper(v, goal);
  return 0;
}

Input

4
1 0 1 0 1
2

Output

4

Complexity Analysis

Time Complexity

O(N), where N is the size of the array.

We traverse through the loop once, and the inner loops take constant time in average case. Thus time complexity is O(N).

Space Complexity

O(1)

Here we are declaring just a handful of variables. Therefore the space taken is constant.

Check out this problem - Subarray With 0 Sum

Conclusion

In this blog, we learned an important Interview problem, namely Binary Subarrays with sum. We discussed two approaches to solve the problem. The first approach is Brute force which takes O(N * N) time. The second approach uses three-pointers which takes O(N) time. Stay tuned to learn more such interesting problems.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Live masterclass