Smallest subarray with sum greater than x

Given an array of integers (A[])  and a number x, find the smallest subarray with sum greater than the given value.

Note: The answer always exists. It is guaranteed that x doesn't exceed the summation of a[i] (from 1 to N).

Example 1:

Input:
A[] = {1, 4, 45, 6, 0, 19}
x  =  51
Output: 3
Explanation:
Minimum length subarray is 
{4, 45, 6}

Example 2:
Input:
A[] = {1, 10, 5, 2, 7}
   x  = 9
Output: 1
Explanation:
Minimum length subarray is {10}

 

method: sliding window

  • Maintain l and r index to store and print these values 
  • Iterate the complete array.
  • Add array elements to current sum (int c)
  • If current sum becomes greater than x, check the length of the subarray(int mi) and if it is min found till now update it,and even  subtract a[l] from subarray and increment l
  • if current sum is less than x, then add a[r] to the subarray and increment r
  • return the min length of the subarray


c++ implementation:

   int sb(int a[], int n, int x)
{ int l=0;int r=0;int c=0;int mi=INT_MAX; while(r<=n) { if(c>x) { if(mi>r-l) mi=r-l; c=c-a[l]; l++; } else { c=c+a[r]; r++; } } return mi; }
Time Complexity: O(n) 
space Complexity: O(1) 



darkmode