Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 17

Description

Shortest Subarray with Sum at Least K

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

Solution

class Solution {
public:
  int shortestSubarray(vector<int>& nums, int k) {
    int answer = INT_MAX;
    deque<pair<long long, int>> dq;
    long long total = 0;
    int current = 0;

    for(auto n : nums) {
      if(n >= 0) {
        dq.push_back({n, 1});
        total += n;
        current += 1;
      } else {
        if(total + n <= 0) {
          dq.clear();
          total = 0;
          current = 0;
          continue;
        } else {
          auto [sum, len] = dq.back();
          dq.pop_back();
          long long currentSum = n + sum;
          int segLen = 1 + len;
          while(dq.size() && currentSum < 0) {
            auto [s, l] = dq.back();
            dq.pop_back();
            currentSum += s;
            segLen += l;
          }

          total += n;
          dq.push_back({currentSum, segLen});
          current += 1;
        }
      }

      while(dq.size() && total >= k) {
        answer = min(answer, current);
        auto [s, l] = dq.front();
        dq.pop_front();
        total -= s;
        current -= l;
      }
    }

    return answer == INT_MAX ? -1 : answer;
  }
};