Binary Subarrays with Sum

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;
}

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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!