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 English aakarshmadhavan 2018-07-10 06:45:59 1015 Initial revision (published)