2 pointer method with prefix sum is getting TLE and brute force solution is passing!


#1

@anshumansingh
Hi Anshuman, based on your previous comment , I have submitted a 2 ptr solution (start ptr, end ptr) along with pref sum. However, it is getting TLE along with partially correct answer. Can you suggest an improvement?

int a=0, b=0;
for(int i=0;i<n;i++)
{
if(A[i]>C)
continue;

    if(a<i)
    a=i;
    
    while(a<n && sum_itoj(pref, i, a)<B)
    a++;
    
    if(sum_itoj(pref, i, a)>C)
    continue;
    
    if(b<a)
    b=a;
    while(b<n && sum_itoj(pref, i, b)<=C)
    b++;
    
    ans+=b-a;
}

#2

2 pointer method with prefix sum will work in O(n) and is the most optimal solution i guess. Also my solution using two pointer got accepted. I think you should look for other possible sources of TLE in your code like any loop which takes O(n^2) or infinite time, etc.
As far as alternative approach is concerned, initially i used an O(nlogn) approach using binary search which also got accepted. Basically, instead of using two pointers to find the range you can use binary search on prefix sum array to pinpoint the valid range for each element.