shivam565's blog

By shivam565, history, 4 years 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?
»
4 years ago, hide # |
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
»
4 years ago, hide # |
 
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 \lt = k$$$.

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