Minimal Subarray That Is More Than A Key

Question

I have an array of integers (not necessarily sorted), and I want to find a continuous subarray whose sum of its values ​​is minimal, but greater than a certain value of K

eg.:

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

output: {4,9}

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

My idea: I still could not find this in O(n) , but all I could think of was O(n^2) time complexity.

Answer 1

Suppose that it can only have positive values.

Then it's easy.

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

Take two indexes, one for the beginning of the subarray and one for the end (one after the end), start with end = 0 and start = 0 . Initialization 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; } 

As both indices only increase, the O(n) algorithm.

Answer 2

Java implementation for positive and negative numbers (not completely sure about negative numbers) that work in O (n) time with O (1) space.

 public static int findSubSequenceWithMinimumSumGreaterThanGivenValue(int[] array, int n) { if (null == array) { return -1; } int minSum = 0; int currentSum = 0; boolean isSumFound = false; int startIndex = 0; for (int i = 0; i < array.length; i++) { if (!isSumFound) { currentSum += array[i]; if (currentSum >= n) { while (currentSum - array[startIndex] >= n) { currentSum -= array[startIndex]; startIndex++; } isSumFound = true; minSum = currentSum; } } else { currentSum += array[i]; int tempSum = currentSum; if (tempSum >= n) { while (tempSum - array[startIndex] >= n) { tempSum -= array[startIndex]; startIndex++; } if (tempSum < currentSum) { if (minSum > tempSum) { minSum = tempSum; } currentSum = tempSum; } } else { continue; } } } System.out.println("startIndex:" + startIndex); return minSum; }