Shortest subarray with sum at least k

Revision en1, by aakarshmadhavan, 2018-07-10 06:45:59
Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

EXAMPLE:
Input: A = [2,-1,2], K = 3
Output: 3
---------
Input: A = [1,2], K = 4
Output: -1
---------
Input: A = [84,-37,32,40,95], K = 167
Output: 3


I have tried 2-pointers/sliding-window but it can't handle negative cases and gives the wrong answer. Can the geniuses of CF help me out on how to approach this problem?

Here is my (non working) code:

public int shortestSubarray(int[] A, int K) {
int ptr = 0;
int sum = 0;
int sol = Integer.MAX_VALUE;
for(int i = 0; i < A.length; ++i){
sum += A[i];
while(sum >= K){
sol = Math.min(sol, i - ptr + 1);
sum -= A[ptr++];
}

}
return (sol == Integer.MAX_VALUE) ? -1 : sol;
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en1 aakarshmadhavan 2018-07-10 06:45:59 1015 Initial revision (published)