CODEWITHSUNDEEP
algorithmdata-structurestime-complexity
user3111412
user3111412

Reputation: 187

Number of subarrays with sum less than or equal a given 'k'

I know a O(n2) soln, can it be done in a better way, as the limit of no of elements in the array is huge is <=100,000

Upvotes: 0

Views: 8930

Answers (3)

Ayush
Ayush

Reputation: 1620

Outflak explained the algorithm for a linear time solution of the problem provided the elements are non-negative quite well.

I came here with the same question as the OP and got my answer after reading outflak's answer, but since there was no code I had to write it up myself.

Hence, I'm adding some Python code along with some explanation for future readers:

left, right, runSum, count = 0, 0, 0, 0

nums = [10,11,30,1009,13]
limit = 35
# Expected answer - 5 ([10], [11], [10,11], [30], [13])

while right < len(nums):
    runSum += nums[right]
    while runSum > limit:
        runSum -= nums[left]
        left += 1
    count += right - left + 1
    right += 1

print(count)

>>> 5

Just to reiterate:

  1. We're making use of a sliding window, with left and right being our two pointers.
    runSum is the accumulated running sum and count is our answer.

  2. At each step, we expand our window by adding nums[right] to runSum.

  3. Then as long as runSum is greater than our allowed limit, we shrink the window by subtracting from the left side of the window, i.e. nums[left].

  4. Finally, right - left + 1 gives us the 'size' of our current valid window, which we add to our count at every step.

Upvotes: 1

GDS
GDS

Reputation: 21

As pointed out by shole, if all elements are non-negative, you can indeed use a "two pointer" technique to solve this problem in O(n).

Basically you have two pointers left and right, initialized both at 0. You increment the right pointer, and keep track of current sum : while current sum inside the sliding window is <= k, you keep incrementing "right". Once the sum of elements inside the window is > k, then you increment left pointer, to reduce the sum inside the window. Each time the window is valid and left=i and right=j, you can say there are j-i more subarrays that are valid (the subarrays beginning at k [i, j] and finishing at j) and which were not counted before.

Upvotes: 0

shole
shole

Reputation: 4094

Yes there is a O(n lgn) algorithm if all elements are non-negative.

  1. Define p[i] be the sum of p[0..i] (We call it prefix sum)
  2. For each i: Binary search maximum j such that p[j] - p[i-1] <= k, add j-i+1 to the counter

Total complexity is O(n) + O(n lgn) = O(n lgn)

Why it works, is because for each i, we are trying to find the maximum range starting from i such that the sum of this range is <= k.

Let this range be [i..j], as all elements are non-negative, so [i..i], [i..i+1], [i..i+2] ... [i..j] are all sub-array which sum is <= k, there are total j-i+1 of them.

We find such range for each i, and keep adding the number of sub-array starting from i which sum <= k

Upvotes: 8

Related Questions