I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!
Problem
- Return the length of the shortest, non-empty, contiguous subarray of
nums
with sum at leastk
.- If there is no non-empty subarray with sum at least k, return -1.
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
Note:
- \$1 <= \text{nums.length} <= 50000\$
- \$-10 ^ 5 <= \text{nums}[i] <= 10 ^ 5\$
- \$1 <= k <= 10 ^ 9\$
Code
#include <vector>
#include <algorithm>
#include <deque>
class Solution {
public:
static int shortestSubarray(std::vector<int> nums, const int k) {
const int length = nums.size();
int shortest = length + 1;
std::deque<int> deque_indicies;
for (int index = 0; index < length; index++) {
if (index) {
nums[index] += nums[index - 1];
}
if (nums[index] >= k) {
shortest = std::min(shortest, index + 1);
}
while (!deque_indicies.empty() && nums[index] - nums[deque_indicies.front()] >= k) {
shortest = std::min(shortest, index - deque_indicies.front());
deque_indicies.pop_front();
}
while (!deque_indicies.empty() && nums[index] <= nums[deque_indicies.back()]) {
deque_indicies.pop_back();
}
deque_indicies.emplace_back(index);
}
return shortest <= length ? shortest : -1;
}
};