Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/862.html

862. Shortest Subarray with Sum at Least K (Hard)

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 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

Input: A = [2,-1,2], K = 3
Output: 3

 

Note:

1. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9

Companies:
Facebook, Goldman Sachs

Related Topics:
Binary Search, Queue

Solution 1. Sliding Window

Let P[i] = A[0] + ... A[i - 1] where i ∈ [1, N]. Our goal is to find the smallest y - x such that P[y] - P[x] >= K.

Let opt(y) be the largest x such that P[y] - P[x] >= K. Two key observations:

1. If x1 < x2 and P[x1] >= P[x2], then we don’t need to consider x1 because if P[y] - P[x1] >= K then P[y] - P[x2] must >= K as well, and y - x2 < y - x1.
2. If opt(y1) = x, then we do not need to consider this x again. If we find some y2 > y1 with opt(y2) = x, then it represents an answer y2 - x which is worse (larger) than y1 - x.

Rule 1 tells us that we just need to keep a strictly increasing sequence P[a] < P[b] < P[c]....

Rule 2 tells us that we can further shrink the sequence from the front whenever the front element P[x] has been used as opt(y).

Algorithm

Maintain a “monoqueue” of indices of P: a deque of indices x_0, x_1, ... such that P[x_0], P[x_1], ... is increasing.

When adding a new index y, we’ll pop x_i from the end of the deque so that P[x_0], P[x_1], ..., P[y] will be increasing.

If P[y] >= P[x_0] + K, then (as previously described) we don’t need to consider this x_0 again, and we can pop it from the front of the deque.

// OJ: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/articles/shortest-subarray-with-sum-atleast-k/
class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int N = A.size(), ans = INT_MAX;
        vector<long> P(N + 1);
        for (int i = 0; i < N; ++i) P[i + 1] = P[i] + A[i];
        deque<int> q;
        for (int y = 0; y < P.size(); ++y) {
            while (q.size() && P[y] <= P[q.back()]) q.pop_back();
            while (q.size() && P[y] >= P[q.front()] + K) {
                ans = min(ans, y - q.front());
                q.pop_front();
            }
            q.push_back(y);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

• Java
• C++
• Python
• Go

• class Solution {
      public int shortestSubarray(int[] A, int K) {
          int length = A.length;
          long[] prefixSums = new long[length + 1];
          for (int i = 1; i <= length; i++)
              prefixSums[i] = prefixSums[i - 1] + A[i - 1];
          int subarrayLength = Integer.MAX_VALUE;
          Deque<Integer> deque = new LinkedList<Integer>();
          for (int i = 0; i <= length; i++) {
              while (!deque.isEmpty() && prefixSums[i] <= prefixSums[deque.peekLast()])
                  deque.pollLast();
              while (!deque.isEmpty() && prefixSums[i] >= prefixSums[deque.peekFirst()] + K)
                  subarrayLength = Math.min(subarrayLength, i - deque.pollFirst());
              deque.offerLast(i);
          }
          return subarrayLength <= length ? subarrayLength : -1;
      }
  }
  
  ############
  
  class Solution {
      public int shortestSubarray(int[] nums, int k) {
          int n = nums.length;
          long[] s = new long[n + 1];
          for (int i = 0; i < n; ++i) {
              s[i + 1] = s[i] + nums[i];
          }
          Deque<Integer> q = new ArrayDeque<>();
          int ans = n + 1;
          for (int i = 0; i <= n; ++i) {
              while (!q.isEmpty() && s[i] - s[q.peek()] >= k) {
                  ans = Math.min(ans, i - q.poll());
              }
              while (!q.isEmpty() && s[q.peekLast()] >= s[i]) {
                  q.pollLast();
              }
              q.offer(i);
          }
          return ans > n ? -1 : ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
  // Time: O(N)
  // Space: O(N)
  // Ref: https://leetcode.com/articles/shortest-subarray-with-sum-atleast-k/
  class Solution {
  public:
      int shortestSubarray(vector<int>& A, int K) {
          int N = A.size(), ans = INT_MAX;
          vector<long> P(N + 1);
          for (int i = 0; i < N; ++i) P[i + 1] = P[i] + A[i];
          deque<int> q;
          for (int y = 0; y < P.size(); ++y) {
              while (q.size() && P[y] <= P[q.back()]) q.pop_back();
              while (q.size() && P[y] >= P[q.front()] + K) {
                  ans = min(ans, y - q.front());
                  q.pop_front();
              }
              q.push_back(y);
          }
          return ans == INT_MAX ? -1 : ans;
      }
  };
  

• class Solution:
      def shortestSubarray(self, nums: List[int], k: int) -> int:
          s = list(accumulate(nums, initial=0))
          q = deque()
          ans = inf
          for i, v in enumerate(s):
              while q and v - s[q[0]] >= k:
                  ans = min(ans, i - q.popleft())
              while q and s[q[-1]] >= v:
                  q.pop()
              q.append(i)
          return -1 if ans == inf else ans
  
  
  

• func shortestSubarray(nums []int, k int) int {
  	n := len(nums)
  	s := make([]int, n+1)
  	for i, x := range nums {
  		s[i+1] = s[i] + x
  	}
  	q := []int{}
  	ans := n + 1
  	for i, v := range s {
  		for len(q) > 0 && v-s[q[0]] >= k {
  			ans = min(ans, i-q[0])
  			q = q[1:]
  		}
  		for len(q) > 0 && s[q[len(q)-1]] >= v {
  			q = q[:len(q)-1]
  		}
  		q = append(q, i)
  	}
  	if ans > n {
  		return -1
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions