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 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
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:
- If
x1 < x2
andP[x1] >= P[x2]
, then we don’t need to considerx1
because ifP[y] - P[x1] >= K
thenP[y] - P[x2]
must>= K
as well, andy - x2 < y - x1
. - If
opt(y1) = x
, then we do not need to consider thisx
again. If we find somey2 > y1
withopt(y2) = x
, then it represents an answery2 - x
which is worse (larger) thany1 - 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;
}
};
-
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 }