Longest Contiguous Subarray with Average Greater than or Equal to k

Question

Consider an array of N integers. Find the longest contiguous subarray so that the average of its elements is greater (or equal) than a given number k.

The obvious answer has O(n^2) complexity. Can we do better?

Answer 1

We can reduce this problem to longest contiguous subarray with sum >= 0 by subtracting k from all values in O(n) time. Now let's calculate prefix sums:

index    0     1     2     3     4     5     6
array          2     -3    3     2     0     -1
prefix   0     2     -1    2     5     5     4

Now this problem is finding the two indices most far apart with prefix_right - prefix_left >= 0. Let's create a new prefix-index array and sort it by prefix, then indices.

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5

We can then do a right-to-left sweep to calculate, for each prefix, the maximum index with prefix greater than or equal to the current prefix:

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5
maxind   6     6     6     6     6     5     5

Now, let's go back to the original prefix array. For each prefix-index pair, we do a binary search on our new array to find the smallest prefix >= the current prefix. We subtract, from maxind of the binary searched prefix, the index of the current prefix to retrieve the best possible sequence length starting at the current index. Take the sequence with the maximum length.

This algorithm is O(n log n) because of the sorting and the n binary searches.

Answer 2

We can solve problem in O(n) time and O(n) space complexity:
I have tried with naive and optimal approach.
In short, the problem involves two steps:
(1) Subtract k from each ar[i] and find cumulative value in new array. Lets call the new array as cumArr[].
(2) Now the problem becomes finding max(j-1) in CumArr[] such that j>i and cumArr[j]>cumArr[i]. This step is a famous question and can be found at lots of places.

Here is the detail with running code: http://codeshare.io/Y1Xc8

There might be small corner cases which can be handled easily.
Let me know your thoughts friends.