Space

Open

From Fieldwork

Scales

862. Shortest Subarray with Sum at Least K

leetcodearrayprefix-sumdequehard

v1

Standard sliding window solutions (O(N)) only work when the array contains non-negative numbers. Because nums can contain negative numbers here, the prefix sum is not monotonic. This solution addresses that specific constraint efficiently.

Prefix Sums: We transform the problem to finding y and x (y > x) such that P[y] - P[x] >= K.
Deque Logic:
- Condition 1 (popleft): Once an index x (from the front of the deque) satisfies the condition with current index y, we calculate the length and discard x. We never need x again because any future y' > y would result in a longer subarray (y' - x > y - x), and we are looking for the shortest.
- Condition 2 (pop): If the current prefix sum P[y] is smaller than the prefix sum at the back of the deque (P[x]), we discard x. Why? Because y has a smaller value (making it easier to reach K) and y is a later index (making the subarray shorter). y is strictly better than x.

Complexity Analysis

Time Complexity: O(N).
Each index from 0 to N is added to the deque exactly once and popped from the deque at most once.
Space Complexity: O(N).
Used for the Prefix Sum array and the Deque.

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # Build Prefix Sum array
        # P[i] represents sum(nums[0]...nums[i-1])
        P = [0] * (n + 1)
        for i in range(n):
            P[i + 1] = P[i] + nums[i]
        
        # Deque stores indices 'i' of the prefix sum array.
        # It is maintained to be monotonically increasing based on P[i].
        dq = deque()
        min_len = n + 1
        
        for y in range(n + 1):
            # 1. Check for valid subarrays ending at y
            # If P[y] - P[dq[0]] >= k, we found a valid subarray.
            # We try to shorten it by popping from the left.
            while dq and P[y] - P[dq[0]] >= k:
                min_len = min(min_len, y - dq.popleft())
            
            # 2. Maintain monotonicity (Optimization)
            # If P[y] <= P[dq[-1]], then index y is a better start point
            # than dq[-1] because y is larger (shorter subarray) 
            # and P[y] is smaller (easier to reach sum k).
            while dq and P[y] <= P[dq[-1]]:
                dq.pop()
            
            dq.append(y)
            
        return min_len if min_len <= n else -1

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeNov 25, 2025