Number of Subarray whose sum greater than given value

Question

Given an array of N integers (positive and negative), find the number of contiguous sub array whose sum is greater or equal to K (also, positive or negative)

I have managed to work out a naive O(N²) solution, is it possible to get better?

Answer 1

Yes, it is possible to do it in O(n log n) time.

1. Let's take a look at prefix sums. A sum of a (L, R] subarray is prefixSum[R] - prefixSum[L].

2. It means that we can count the number of such L and R that L < R and prefixSum[R] - prefixSum[L] >= K, which means prefixSum[L] <= prefixSum[R] - K.

3. Let's iterate over the array of prefix sums from left to right and maintain a data structure that can do the following operations efficiently :

   • Add a new element.
   • Find the number of elements less than or equal to a given number.

   We can use a balanced binary search tree for this purpose.

Here is a pseudo-code of this solution:

tree = an empty search tree
result = 0
// This sum corresponds to an empty prefix.
prefixSum = 0
tree.add(prefixSum) 
// Iterate over the input array from left to right.
for elem <- array:
    prefixSum += elem
    // Add the number of subarrays that have this element as the last one
    // and their sum is not less than K.
    result += tree.getNumberOfLessOrEqual(prefixSum - K) 
    // Add the current prefix sum the tree.
    tree.add(prefixSum)
print result

The time complexity is O(n log n) because there are O(n) add and count number of elements operations, and each of them can be done in O(log n).