LeetCode #862: Shortest Subarray with Sum at Least K (C/C++).

hard

source: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
C/C++ Solution to LeetCode problem 862. Shortest Subarray with Sum at Least K.

Problem

---

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.

Examples

---

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 <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

Solution

---

class Solution {
public:
  int shortestSubarray(vector<int>& nums, int k) {
    deque<int> dq;
    vector<long long> pSum(nums.size(), 0);
    long long sum = 0;

    int minSize = nums.size() + 1;
    for(int i=0; i<nums.size(); i+=1) {
      sum += nums[i];
      pSum[i] = sum;

      if (pSum[i] >= k)
        minSize = min(minSize, i + 1);

      while(!dq.empty() && pSum[i] - pSum[dq.front()] >= k) {
        minSize = min(minSize, i - dq.front());
        dq.pop_front();
      }

      while(!dq.empty() && pSum[dq.back()] >= pSum[i])
        dq.pop_back();

      dq.push_back(i);
    }

    return minSize == nums.size() + 1 ? -1 : minSize;
  }
};