Skip to content

Shortest Subarray with Sum at Least K⚓︎

Link

Description⚓︎

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:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

Solution⚓︎

See reference (Chinese).

 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
27
28
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        int res = n + 1;

        vector<long> sum(n + 1, 0L);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        deque<int> que;
        for (int i = 0; i <= n; i++) {
            while (!que.empty() && sum[i] - sum[que.front()] >= k) {
                res = min(res, i - que.front());
                que.pop_front();
            }

            while (!que.empty() && sum[que.back()] >= sum[i]) {
                que.pop_back();
            }

            que.push_back(i);
        }

        return res == n + 1 ? -1 : res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).