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(N2) solution, is it possible to get better?
-
What's the star for?Jason Nordwick– Jason Nordwick2015-02-01 23:10:19 +00:00Commented Feb 1, 2015 at 23:10
-
Do the subarrays have to be contiguous?Imran– Imran2015-02-01 23:27:34 +00:00Commented Feb 1, 2015 at 23:27
-
@jasonN oops . typo. will fix thatfyquah95– fyquah952015-02-02 00:14:11 +00:00Commented Feb 2, 2015 at 0:14
-
@Imran yes. will add that to the questionfyquah95– fyquah952015-02-02 00:14:47 +00:00Commented Feb 2, 2015 at 0:14
Add a comment
|
2 Answers
Yes, it is possible to do it in O(n log n) time.
Let's take a look at prefix sums. A sum of a
(L, R]subarray isprefixSum[R] - prefixSum[L].It means that we can count the number of such
LandRthatL < RandprefixSum[R] - prefixSum[L] >= K, which meansprefixSum[L] <= prefixSum[R] - K.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).
2 Comments
void
This is an amazing soln. If somebody has a Python implementation of this lying around, do share
A_ Myth963
instead of creating the balanced binary search tree, we can use Ordered set -> and then the complexity will be O(n) for the entire code.
Here is another solution, which uses Divide and Conquer method. Time complexity is O(n lg n).
The first two steps are just like above post:
Create prefix sums, let's call them
prefixSum[].It means that we have to count the number of such
LandRthatL < RandprefixSum[R] - prefixSum[L] >= K.Now, let's make another array, let's call it
arr[], wherearr[i] = prefixSum[N - 1 - i]forifrom0toN - 1. This means that we are creating a reversedprefixSum[]array.
Now we have to count the number of such i and j that i < j and arr[i] - arr[j] >= K. To do this, we'll use Merge Sort (which uses D & C method):
Suppose that we have:
MergeSort(arr, left, right):
mid = (left + right) / 2
MergeSort(arr, left, mid)
MergeSort(arr, mid + 1, right)
Merge(arr, left, mid, right)
In Merge function, we have to add this:
i = left - mid # Index for the left array
j = mid + 1 - right # Index for the right array
if (arr[i] >= arr[j]):
if (arr[i] >= arr[j] + K):
count += (mid - i + 1)
# Because arr[] from i to mid are all
# greater or equal to arr[i] so if arr[i] >= arr[j] + K
# then arr[] from i to mid are all >= arr[j] + K.
else:
if (arr[i] >= arr[j] + K): # K can be negative.
count += mid - i + 1;
The idea is the same to count Inversion in an array
https://www.cdn.geeksforgeeks.org/counting-inversions/
