Find Number of Sub-arrays with sum is greater than or equal to K

Last Updated on June 9, 2023 by Mayank Dham

Finding the number of subarrays with a sum greater than or equal to a given value K is a common problem in array manipulation. The task involves determining the count of contiguous subarrays within a given array where the sum of elements in the subarray meets the specified condition. This problem can be efficiently solved using approaches such as prefix sum or the two-pointers technique

Given an array of N elements, print the total number of sub-arrays whose sum value is greater than or equal to K. Also, it is recommended to go through from Subarray with given sum problem for better understanding.

Understand with the Example:

Input : N = 5, K = 3
        A[] = [1 2 3 4 5]

Output : 13

Explanation :

There are 13 sub-arrays whose sum is greater than or equal to 3

(3), (4), (5) 

(1 2), (2 3), (3 4), (4 5),

(1 2 3), (2 3 4), (3 4 5), 

(1 2 3 4), (2 3 4 5), (1 2 3 4 5)

The only two sub-arrays whose sum is less than 3 are (1) and (2).

Brute Force Method to Find Number of Subarrays with Sum Greater than or Equal to K:

1. A simple brute force solution is to generate all the sub-arrays and check whether their sum is greater than or equal to K or not.

2. There are

   

   number of sub-arrays in an array.

3. Time Complexity of this approach would be quadratic i.e. O(N^2).

NOTE: If N <= 10³, it would work fine but for greater values of N, it would result in TLE (Time Limit Exceeded).

SOLUTIONS:

#include <stdio.h> 

int subarrays(int arr[],int n,int k) 
{ 
    int count = 0; 

    for (int i = 0; i < n; i++) 
    { 
      int sum = 0; 
      for (int j = i; j < n; j++) 
      {
        sum += arr[j];
        if (sum  >= k) 
        { 
            count++; 
        } 

      } 
    } 

    return count; 
} 

int main() 
{ 
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d %d",&n,&k);
    int arr[n];
    for(int i=0;i<n;i++)
      scanf("%d",&arr[i]);
    printf("%d\n",subarrays(arr,n,k));
  }
} 

#include <bits/stdc++.h> 
using namespace std; 


int subarrays(int arr[],int n,int k) 
{ 
    int count = 0; 

    for (int i = 0; i < n; i++) 
    { 
      int sum = 0; 
      for (int j = i; j < n; j++) 
      {
        sum += arr[j];
        if (sum  >= k) 
        { 
            count++; 
        } 

      } 
    } 

    return count; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    cout<<subarrays(arr,n,k)<<"\n";
  }
  return 0;
}

Time Complexity: O(N²)

Space Complexity: O(1)

Efficient Method to Find Number of Subarrays with Sum Greater than or Equal to K:

1. In order to find the total no. of subarrays that have sum value greater than equal to K, instead we can find total subarrays that have value less than K, the difference between total no of subarrays and our calculated subarrays would be our answer.

2. The idea is to use Sliding Window Technique.

3. We make use of two pointers that point to the starting and the ending of this window, start and end.

4. Initially both the pointers point to the beginning of the array i.e. 0^th index.

5. Now whenever we add an element, there arises two possible cases –
   >1. If the sum is less than K, we will increment our end pointer by 1 and the value of (end - start) will give us the current count of subarrays with value less than K. Because there are as many subarrays as the length of the window.
   >
   >2. If the sum is greater than or equal to K, we need to subtract the starting element from the sum so that it becomes less than K again and increment our start pointer by 1.
   >
   >3. Keep repeating steps 1 and 2 until we reach the end of the array.

Program to find number of subarrays with sum greater than k or Equal to K:

A[] = [1, 2, 3, 4, 5]
K = 3

start = 0
end = 0
sum = A[start] = 1
count = 0

(start < n) and (end < n) and (sum < K) 
end ++ => end = 1
count = count + (end - start) = 0 + 1 - 0 = 1
sum = sum + A[end] = 1 + 2 = 3
start = 0

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 3 - 1 = 2
start ++ => start = 1
end = 1

(start < n) and (end < n) and (sum < K) 
end ++ => end = 2
count = count + (end - start) = 1 + 2 - 1 = 2
sum = sum + A[end] = 2 + 3 = 5
start = 1

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 5 - 2 = 3
start ++ => start = 2
end = 2

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 3 - 3 = 0
start ++ => start = 3
end = 2

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 0 - 4 = -4
start ++ => start = 4
end = 2

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = -4 - 5 = -9
start ++ => start = 5
end = 2

Since (start >= n), we will stop here and count = 2 is the number of subarrays
which have value less than K = 3

Count of subarrays with sum greater than or equal to K can be calculated by subtracting this calculated count by total number of sub-arrays.

SOLUTIONS:

#include <stdio.h>

int kmin(int arr[],int n,int k)
{
  int start = 0, end = 0, sum = arr[0], count = 0;
  while(start<n && end<n)
  {
    if(sum<k)
    {
      end++;
      if(end>=start)
        count += end-start;
      if(end<n)
        sum += arr[end];
    }
    else
    {
      sum -= arr[start];
      start++;
    }
  }
  return count;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d%d",&n,&k);
    int arr[n];
    for(int i=0;i<n;i++)
    {
      scanf("%d",&arr[i]);
    }
    long long res = ((long long)n*(n+1))/2;
    printf("%lld\n",res-kmin(arr,n,k));
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int kmin(int arr[],int n,int k)
{
  int start = 0, end = 0, sum = arr[0], count = 0;
  while(start<n && end<n)
  {
    if(sum<k)
    {
      end++;
      if(end>=start)
        count += end-start;
      if(end<n)
        sum += arr[end];
    }
    else
    {
      sum -= arr[start];
      start++;
    }
  }
  return count;
}
int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
      cin>>arr[i];
    }
    long long res = ((long long)n*(n+1))/2;
    cout<<res-kmin(arr,n,k)<<"\n";
  }

  return 0;
}

import java.util.*;
import java.io.*;


public class Main {

  public static long kmin(int arr[],int n,int k)
    {
      int start = 0, end = 0, sum = arr[0], count = 0;
      while(start<n && end<n)
      {
        if(sum<k)
        {
          end++;
          if(end>=start)
            count += end-start;
          if(end<n)
            sum += arr[end];
        }
        else
        {
          sum -= arr[start];
          start++;
        }
      }
      return count;
}
  public static void main(String args[]) throws IOException {

    int t;
        Scanner sc=new Scanner(System.in);
        t=sc.nextInt();

        while(t>0){
            int n,k;
            n=sc.nextInt();
            k=sc.nextInt();
            int arr[]=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=sc.nextInt();
            }
            long res = (n*(n+1))/2;
            long p=kmin(arr,n,k);
            System.out.println(res-p);
            t--;
      }
  }
}

Conclusion
Finding the number of subarrays with a sum greater than or equal to a given value K is a problem that can be efficiently solved using approaches such as prefix sum or the two-pointers technique. These techniques allow us to iterate through the array and count the valid subarrays by maintaining the necessary information about the sum of elements. By leveraging prefix sums or employing the two-pointers technique, we can achieve a time complexity of O(n), effectively determining the number of subarrays that meet the specified condition. This problem is commonly encountered in array manipulation tasks and can be solved with optimized algorithms, providing an efficient solution to count the subarrays with a sum greater than or equal to K.

Frequently Asked Questions

Q1. Can this problem be solved using brute force?
Yes, this problem can be solved using a brute force approach by generating all possible subarrays and checking their sums. However, the brute force approach has a high time complexity of O(n^3) and is not efficient for large arrays. Hence, optimized techniques like prefix sum or the two-pointers approach are preferred.

Q2. What is the prefix sum technique?
The prefix sum technique involves precomputing an array where each element represents the sum of elements up to that index. By using this preprocessed information, the sum of any subarray can be computed in constant time. It enables faster computation of subarray sums, reducing the time complexity of the problem.

Q3. How does the two-pointers technique work?
The two-pointers technique involves maintaining two pointers, "start" and "end," which represent the starting and ending points of the subarray. By incrementing the "end" pointer while adding elements to the sum, and incrementing the "start" pointer while subtracting elements, the subarray boundaries are adjusted to find valid subarrays. This technique reduces the time complexity to O(n) as it traverses the array only once.

Q4. Are there any trade-offs when using the two-pointers technique?
The two-pointers technique provides an efficient solution with a time complexity of O(n). However, it requires the array elements to be non-negative or have specific properties to maintain correctness. If negative elements are present, alternative approaches or modifications may be necessary.

Q5. Can this problem be solved in linear time complexity?
Yes, the problem can be solved in linear time complexity using optimized approaches like prefix sum or the two-pointers technique. These approaches allow efficient traversal of the array, resulting in a time complexity of O(n), where n is the size of the array.