Блог пользователя aakarshmadhavan

Автор aakarshmadhavan, история, 4 месяца назад, По-английски,
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;
    }
 
 
 
 
  • Проголосовать: нравится  
  • +28
  • Проголосовать: не нравится  

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      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!

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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;
    
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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).

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

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.