aakarshmadhavan's blog

By aakarshmadhavan, history, 2 months ago, In English,
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;
    }
 
 
 
 
  • Vote: I like it  
  • +28
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Two pointer method should work. When you are advancing the right pointer, if the sum becomes negative, then move the left pointer to the current index and update the sum to 0, because it is never better to take a subarray with negative sum. Rest of it is the same as normal two pointers on an array with positive integers.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    This would fail for {5,  - 4, 1, 2} and K = 3.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      It works for that case, but I get your point. The logic fails for sample 3 because we can not directly subtract a[1] when l=1, r=5, but we can remove both a[1] and a[2]

      My bad!

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Complexity of the solution is O(N*log(N))

For every index i we'll try and find the smallest length subarray such that it ends at position i and it's sum is >= k. pref[i] is equal to the prefix sum of the array that ends at position i.

So if we're looking at position i and we don't plan on taking the entire prefix we know that there has to be some previous prefix sum at index j such that: pref[i] — pref[j] >= k. Reforming this inequality we get: pref[i] — k >= pref[j]. So what we're essentially looking for at every i is the largest j such that it's prefix sum is <= pref[i] — k (the largest j so that we can cut off as much of the array as possible). This problem can be solved with a segment tree that handles point updates and stores the max on a range.

I think that solves the problem and I hope that made sense.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It turns out there is an O(N) solution, can anyone give some hints for that?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Keep a dequeue of the 'best' prefix sums found so far. This will be increasing both in index as well as in value. When we go from left to right, we add new prefix sums to the back (making sure it stays increasing in value) and remove prefix sums from the front (if we can use it here, it will never be better to use it later).

    The code will look something like this:

    long long sum = 0;
    deque<pair<int,long long>> q;
    int ret = INT_MAX;
    for(int i = 0; i < n; ++i ) {
    	while( !q.empty() && q.back().second >= sum )
    		q.pop_back();
    	q.push_back(make_pair(i,sum));
    	sum += A[i];
    	while( !q.empty() && q.front().second <= sum - k) {
    		ret = min(ret, i + 1 - q.front().first);
    		q.pop_front();
    	}
    }
    return ret == INT_MAX ? -1 : ret;
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey there,

      Thanks for the reply and solution. Would you be willing to share why you thought of these things so I can get an idea of your thought process and apply it to future problems?

      Thanks

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        The first step I took is to think of the problem in terms of prefix sums. This is a very common approach in problems dealing with sums over subarrays, so the reason I thought of is is experience.

        The second step I took is to notice that were only interested in the last position in the list that has a value of at least x. Therefore, we can remove items from the list when there is a later smaller prefix sum. This will make the list increasing in both index and value. This is also quite a common trick, but I think it should be possible to come up with this even if you haven't seen it before.

        Now for a given end position we can binary search the list to find the best start position for it. If we want to make it linear, we somehow have to get rid of the binary search. Suppose the optimal start position for a given end position is in the middle of the list. If we could remove the elements before, this would make the algorithm linear. The problem with this is that those elements before could be the optimal starting positions for some later ending positions. The third step is to notice that allthough this indeed might cause the algorithm to miss some best local minimums, it will never cause the algorithm to miss a global minimum.

        The way to make algorithm linear (drop elements before current optimum) is also quite a common trick, but one I think you should be able to come up with even if you haven't seen it before. The most difficult part of this problem for me was to see why this works (local minimums vs global minimums).

        So in conclusion, to solve this problem in linear time I think you have to have some experience (to know the prefix sums technique), make some logical simplifications (here experience helps) and finally make the observation why this works (the creative, thinking part needing intuition and problem understanding).

»
2 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

There’s another easy solution with O(nlogn). You can check in linear time if there exists a subsequence of length l with the sum >= k (with two pointers) and then apply binary search to find the most optimal length.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why did I get so many downvotes? Is my solution wrong?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh well I just realised it doesn't work Sorry, my bad