VasuOberoi's blog

Unable to find a O(N) solution to this problem
By VasuOberoi, history, 3 years ago, In English

**** Problem: longest sub-array having sum at most k?

If all the array elements are positive then this problem is easily solvable using two pointers. for ex:

Let's say the array look like this a=[10,30,40,7,1] and k=48.

Solution: We keep two pointers l and r and we will always expand our sub-array with rth pointer and shrink from lth pointer

Iterations:

l=0,r=0 a[l---r]= 10 since 10<=48 we update our ans as 1 and we increment the rth pointer l=0,r=1 a[l---r]= [10,30] since 10+30<=48 we update our ans as 2 and we again increment the rth pointer. l=0,r=2 a[l---r]= [10,30,40] since 10+30+40>48 we will shrink our window by incrementing the lth pointer untill sum<=k. ie [10,30,40] to [30,40] still sum>k so we reduce the window to [40] l=2,r=2 a[l----r]=40

l=2,r=3 a[l---r]= [40,7] since 40+7<=48 we increment the rth pointer l=2,r=4 a[l---r]= [40,7,1] since 40+7+1<=48 we update our answer as 3.

This problem is also covered in the two pointers section in code forces edu.

But the problem with this algorithm is it does not work if the array contains negative elements because we are not assure that shrinking the window size always make our sum less positive as our lth pointer can be very big negative value as well. Thus removing the lth pointer here makes our sum more positive.

for ex: a=[-5,-4,-3,16,1,-6,-4,50] and k=3

In above example we can clearly see that the subarray[0,6]=[-5,-4,-3,16,1,-6,-4] is longest having sum<=3

But if we go by above algorithm we will not get this as our answer because when our rth pointer reaches 16 ie a=[-5,-4,-3,16] sum=4>k so we will shrink our window to [-4,-3,16] sum=9>k again we will shrink window to [-3,16] still sum>k.At the end we will be left with empty window ie l=r=3.

Now here we will not get accurate answer as l is increased to 3.

For this problem the only solution that comes into mind is O(N*N) ie trying all poss sub-arrays and checking whether sum<=k and finding largest.

If anyone have a better way of solving this please suggest.Thanks in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it
  1. Use prefix sums
  2. Prefix_sum[r] — prefix_sum[l] <= k
  3. Prefix_sum[r] — k <= prefix_sum[l]
  4. Use coordinate compression for prefix_sum[i], prefix_sum[i] — k, 0
  5. Use segment tree on coordinate compression and take minimum l for i on suffix
  6. N log N
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    We can simply make suffix minimum over prefix sums (to avoid segment tree), ( suff[i] means min(pre[i],pre[i+1]...pre[n]) ). Then for every pre[i], just binary search over suffix minimum to find highest index j (j>=i) such that suff[j]<=k+pre[i]. (Note that suffix minimum will be an increasing sequence.)

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Suppose the optimal interval is $$$[L \ldots R]$$$. Then there can be no index $$$x \gt R$$$ with $$$\sum_{i \in [R+1 \ldots x]} a_i \leq 0$$$, since otherwise $$$[L \ldots x]$$$ would be a better interval. You can precalculate the values $$$R$$$ that satisfy this condition in $$$O(n)$$$ and then the two-pointers/sliding-window idea will just work: Whenever you want to increase $$$R$$$, you can increase it all the way to the next value $$$R'$$$ that satisfies the condition, and doing so cannot decrease the sum on the current interval because otherwise $$$x=R'$$$ would disprove the condition for $$$R$$$.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    By precalculating do you mean this suffix[i------n]<=0 or suffix[i-----n]>0.

    I am not able to understand your approach. At any point, we will check for the maximum R such that afterward including the R+1 ----n index would not work. Please Explain.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can do it in O(n) with an ok constant.

s[0] = 0

s[i] = v[1] + .. + v[i]

u[i] = s[i] - k

For each i I am interested in the smallest j < i such as s[j] >= u[i] (if it exists).

If I have two indices j, z in s[], j < z, both satisfying the request for i:

j < i, s[j] >= u[i] and z < i, s[z] >= u[i],

then I would always prefer j over z, because it would give me a longer subsequence.

Radix sort in increasing manner u[1], .., u[n].

Now go with j = [0, n] through s[], and for each j advance as much as possible into u[] (from the last point you stopped at with j-1).

Basically, pick out as many small u[]s as possible with s[0] = 0, then pick out the remaining ones with s[1], ...

I hope that the following code is correct: https://ide.geeksforgeeks.org/1eFqH6CvTg

Do you have a problem link? Thank you!

→ Reply