shivam565's blog

By shivam565, history, 21 month(s) ago, In English

How to find total number of subarrays with sum atmost k?

Constrains :
-1e4 <= a[i] <= 1e4
1 <= n <= 1e5

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

| Write comment?
»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

We can use sliding window technique to solve the problem.
Here, i and j represent starting and ending points of the sliding window.
Initially i = j = 0.
Now, we will traverse the whole array and try to add elements.

  • If sum < k, j++. So, number of sub-arrays produced = j-i. Also add arr[j] to the sum.
  • If sum >= k, we will subtract arr[i] from sum so that again sum<k. So, i++.
CODE
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Convert the statement to it's equivalent in terms of prefix sums i.e $$$pre_r - pre_l <= k$$$.

Now iterating over $$$r$$$, we need to find number of $$$l$$$ such that $$$pre_l >= pre_r - k$$$, which can be computed using ordered set of all $$$pre_l$$$.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    but in this case, I have to iterate on all the prefix values >= pre(r)-k. How you will handle this thing while iterating the array?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      use pbds!

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You can use pbds or alternatively, compress the values of the prefix sum and use a data structure like segment tree or fenwick tree to count the values.