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?
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.