Binary search prefix sum array problem

help
,
1

I am unable to understand this editorial from codemonk series.
Please explain in detail with an example.

Thank you.

1 Like
2

I didn’t read the editorial.
But I will share my solution.

  • We want to calculate the max value of k such that each contiguous subarray sum of length k is not greater than X.
  • We can find the required max k using binary search, because if current k satisfies the condition, a higher value of k may also satisfy the condition.
    Also, if current k, doesn’t satisfy the condition, there is no way the subarray sum will be less than or equal to x for subarray with length greater than k since array contains all positive elements.
  • Now, the question is how to check for certain ‘k’ whether it satisfies the condition or not.
    We can do this in O(n) if we precalculate prefix sums of array.
    Then for each k length subarray, we will calculate the sum of that subarray using prefix sum array.
    Eg: A={1,3,2,5,6}
    Prefix Sum Array PA={1,4,6,11,17}
    We will loop from 0-index to (n-k) index, and check if,
    PA[i+k-1]-PA[i-1] <=X
    where PA[i+k-1]-PA[i-1] gives the sum of subarray of length k starting from index i
    Like subarray sum for i=2 for k=3 is:
    PA[4]-PA[1]=17-4=13

If for each i from 0 to (n-k) the sum is <=X,

  • We will try to search if there is a higher k possible and hence set
    low=mid+1
    And will save the current value of mid in a variable, in case there wasn’t any
    higher k we shouldn’t miss current satisfying k.

Else

  • We will try for lower values of k by setting high=mid-1



See my code for clarity: 
long long n,x;
cin>>n>>x;
long long p[n]={0};
for(int i=0;i<n;i++)
{
    long long temp;
    cin>>temp;
    if(i==0)
    p[0]=temp;
    else p[i]+=p[i-1]+temp;
}

long long l=1,r=n,mid=-1;
long long ans=-1;
while(l<=r)
{
    mid=(l+r)>>1;
   
    bool possible=true;
    for(int i=0;i<=(n-mid);i++)
    {
        long long sum=(i>0)?(p[i+mid-1]-p[i-1]):(p[i+mid-1]);
        if(sum>x)
        {
            possible=false;
            break;
        }
    }
    if(possible)
    {    
        ans=mid;
        l=mid+1;
    }
    else
    {
        r=mid-1;
    }
}
cout<<ans<<endl;

Total time complexity: O(nlgn)

If you still have any doubt, feel free to ask. :slight_smile:

6 Likes
3

Thank you so much. I was stuck on this problem for a long time. Now it makes a lot more sense.

2 Likes