Must see C++ O(n) Solution using sliding window technique


#1

First find number of subsets less than or equal to k using func() using sliding window. After that func(B-1) = Number of subarray with sum <= B-1
func© = Number of subarray with sum <= C
If we subtract these two we will get exact number of subarray having range [B, C] inclusive.
Sliding window.:- Maintain a j for every I in array so that values from j to i always have sum <= k.
if(sum >k) found move j to right maintaining same i so that we get a particular j for which sum(j->i) <= k.
// Here is code

int func(vector a, int k)
{
int n = a.size();
int j = 0;
int cou = 0;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum = sum+a[i];

    while(j <= i && sum > k)
    {
        sum = sum-a[j];
        j++;
    }

    cou = cou + (i-j+1);
}

return cou;

}
int Solution::numRange(vector &a, int b, int c) {

int ans = func(a, c)-func(a, b-1);
return ans;

}


#2

time complexity for this code is O(n^2) not O(n);


#3

No it is O(n) because j is getting initialised only once and going till n.


#4

Thanks! now i get this.