Shortest Subarray with Sum at Least K

Leetcode Problem:

• Shortest Subarray with Sum at Least K

Summary

• Given an integer array and an integer k, return the length of the shortest non-empty subarray with a sum of at least k.

Approach

• Use a deque to store the prefix sum and its corresponding end index
• Iterate through the array, updating the prefix sum and checking if it's greater than or equal to k
• If it is, update the result with the minimum length
• If the prefix sum minus the front element is greater than or equal to k, remove the front element from the deque
• If the back element's prefix sum is greater than the current prefix sum, remove it from the deque
• Finally, return the result or -1 if no such subarray exists.

Complexity

• O(n) where n is the length of the array

Explanation

• The time complexity is O(n) because we're doing a single pass through the array
• The space complexity is O(n) for storing the deque.

Solution Code:

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        int res = INT_MAX;
        long long curSum = 0;
        deque> q; // (prefix_sum, end_idx)
        for(int r = 0; r < nums.size(); r++){
            curSum += nums[r];

            if(curSum >= k){
                res = min(res, r + 1);
            }

            while (!q.empty() && curSum - q.front().first >= k){
                auto [prefix, endIdx] = q.front();
                q.pop_front();
                res = min(res, r - endIdx);
            }
            while (!q.empty() && q.back().first > curSum) {
                q.pop_back();
            }
            q.push_back({curSum, r});
        }
        
        return res == INT_MAX ? -1 : res;
    }
};