Minimum Subarray which is larger than a Key

Question

I have an array of integers (not necessarily sorted), and I want to find a contiguous subarray which sum of its values are minimum, but larger than a specific value K

e.g. :

input : array : {1,2,4,9,5} , Key value : 10

output : {4,9}

I know it's easy to do this in O(n ^ 2) but I want to do this in O(n)

My idea : I couldn't find anyway to this in O(n) but all I could think was of O(n^2) time complexity.

Answer 1

Let's assume that it can only have positive values.

Then it's easy.

The solution is one of the minimal (shortest) contiguous subarrays whose sum is > K.

Take two indices, one for the start of the subarray, and one for the end (one past the end), start with end = 0 and start = 0. Initialise sum = 0; and min = infinity

while(end < arrayLength) {
    while(end < arrayLength && sum <= K) {
        sum += array[end];
        ++end;
    }
    // Now you have a contiguous subarray with sum > K, or end is past the end of the array
    while(sum - array[start] > K) {
        sum -= array[start];
        ++start;
    }
    // Now, you have a _minimal_ contiguous subarray with sum > K (or end is past the end)
    if (sum > K && sum < min) {
        min = sum;
        // store start and end if desired
    }
    // remove first element of the subarray, so that the next round begins with
    // an array whose sum is <= K, for the end index to be increased
    sum -= array[start];
    ++start;
}

Since both indices only are incremented, the algorithm is O(n).