LC 0862 [H] Shortest Subarray with Sum at Least K - ALawliet/algorithms GitHub Wiki
understand LC 0209 [M] Minimum Size Subarray Sum first
- we use prefix sum because the index can jump
- we use a deque() to enhance the sliding window technique to pop from the front
def shortestSubarray(self, A, K):
N = len(A)
B = [0] * (N + 1)
for i in range(N):
B[i + 1] = B[i] + A[i]
d = deque()
res = N + 1
for i in range(N + 1):
while d and B[i] - B[d[0]] >= K:
res = min(res, i - d.popleft())
while d and B[i] <= B[d[-1]]:
d.pop()
d.append(i)
return res if res <= N else -1
class Solution:
def shortestSubarray(self, A: List[int], K: int) -> int:
n = len(A)
pre_sums = [0]
for i in range(n):
pre_sums.append(A[i] + pre_sums[-1]) # range sum
# maintain an increasing queue (deque so we can remove the front when we don't need it anymore)
# such that we pop when we get an increasing sequence then a smaller number
# because that number at the end of the queue create the biggest difference and is the closest to the current index therefore shortest
inc_q = deque()
ans = sys.maxsize
for right, s in enumerate(pre_sums):
while inc_q and s - pre_sums[inc_q[0]] >= K:
ans = min(ans, right - inc_q.popleft())
while inc_q and s <= pre_sums[inc_q[-1]]:
inc_q.pop()
inc_q.append(right)
return ans if ans < sys.maxsize else -1