862. Shortest Subarray with Sum at Least K

Posted on Edited on In

862. Shortest Subarray with Sum at Least K

Description

Difficulty: Hard

Related Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

1
2
Input: nums = [1], k = 1
Output: 1

Example 2:

1
2
Input: nums = [1,2], k = 4
Output: -1

Example 3:

1
2
Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= 109

Hints/Notes

  • preSum + monotonic queue

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        vector<long> preSum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int left = 0, right = 0, res = INT_MAX;
        deque<long> minQ;
        while (right <= nums.size()) {
            while (!minQ.empty() && preSum[right] < minQ.back()) {
                minQ.pop_back();
            }
            minQ.push_back(preSum[right]);
            while ((preSum[right] - minQ.front() >= k) && left < right) {
                res = min(res, right - left);
                if (preSum[left] == minQ.front()) {
                    minQ.pop_front();
                }
                left++;
            }
            right++;
        }
        return res == INT_MAX ? -1 : res;
    }
};