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.

&nbsp;
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

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	-105 &lt;= nums[i] &lt;= 105
	1 &lt;= k &lt;= 109


# 1. we can not use sliding window to solve the problem, because the numbers in nums can be negative, 
# the numbers in sliding window are not always incrementing
# ex [8,-4,3,1,6], 10

# 2. prefixsum2 - prefixsum1 >= k is used to find a subarray whose sum >= k.
# 3. monotonic queue is used to keep the prefix sums are in the incrementing order
# 4. If the diffenence between the cur and the tail of monotonic queue is greater than or equal to k, we can find the shortest length of the subarray at this time.

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        prefixsum = [0]
        monoq = deque()
        minLen = float('inf')
        # to calculate prefix sum
        for n in nums:
            prefixsum.append(n+prefixsum[-1])
        for idx, cur in enumerate(prefixsum):
            while monoq and prefixsum[monoq[-1]] >= cur: monoq.pop() # to maintain monotonic queue

            # If the diffenence between the head and the tail of monotonic queue is greater than or equal to k, we can find the shortest length of the subarray at this time.
            while monoq and cur-prefixsum[monoq[0]]>=k: 
                minLen = min(minLen, idx-monoq.popleft())
            monoq.append(idx)
        return -1 if minLen == float('inf') else minLen
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        
         TreeMap<Long, Integer> maps = new TreeMap<>();
         long sum = 0l;
         int min = nums.length + 1;
		 
         maps.put(0l, -1);
        
         for(int i = 0; i < nums.length; i++) {
             sum += nums[i];ntry(sum - k) != null) 
			       min = Math.min(min, i - maps.floorEntry(sum - k).getValue()); 
            while(!maps.isEmpty() && maps.lastEntry().getKey() >= sum) 
			       maps.remove(maps.lastEntry().getKey());
        
            maps.put(sum, i);
         }
        
        return min == (nums.length + 1) ? -1 : min;
    }
}
class Solution {
public:
    //2-pointer doesnt work on neg elements
    //Using mono deque to solve sliding window
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        int minsize = INT_MAX;
        vector<long> prefixsum(n,0);
        deque<int> dq;

        prefixsum[0] = nums[0];
        for(int i = 1;i<n;i++) prefixsum[i] = prefixsum[i-1] + nums[i];

        for(int i = 0;i<n;i++){
            if(prefixsum[i]>=k)
                minsize = min(minsize,i+1);

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

            while(!dq.empty() && prefixsum[i]<=prefixsum[dq.back()]){
                dq.pop_back();
            }

            dq.push_back(i);
        }
        return (minsize==INT_MAX) ? -1 : minsize;
    }
};
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var DoublyLinkedList = function(sum = "DUMMY", index = "DUMMY") {
    this.property = {sum, index}
    this.prev = null
    this.next = null
}

DoublyLinkedList.prototype.deque = function() {
    const dequeNode = this.next

    this.next = dequeNode.next
    dequeNode.next.prev = this

    dequeNode.next = null
    dequeNode.prev = null
    return dequeNode
}

DoublyLinkedList.prototype.pop = function() {
    const dequeNode = this.prev

    this.prev = dequeNode.prev
    dequeNode.prev.next = this

    dequeNode.next = null
    dequeNode.prev = null
    return dequeNode
}

DoublyLinkedList.prototype.push = function(node) {
    const prev = this.prev
    const next = this

    node.prev = prev
    node.next = next

    prev.next = node
    next.prev = node
}

var shortestSubarray = function(nums, k) {
    // Steps :-
    // Initalize 3 vaiables :- sum = 0, subArrayLength = Infinity, queue -> []

    const dummyHead = new DoublyLinkedList()
    const dummyTail = new DoublyLinkedList()
    dummyHead.next = dummyTail
    dummyTail.prev = dummyHead

    let queueSize = 0

    let subArraySize = Number.MAX_SAFE_INTEGER
    let sum = 0
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i]

        // Gives one possible answer, if sum is greater than or
        // equal to k
        if (sum >= k)
            subArraySize = Math.min(subArraySize, i+1)

        let lastDequeued

        // Reduce the queue from left till the sum of elements from
        // first index of queue till last index of queue is less than k
        // Each time we constantly update the lastdequeued element
        // As the last lastdequeued will satisfy sum - lastDequeued.sum >= k
        // Thus the range would be i-lastDequeued.property.index
        // (without lastDequeued.property.index)
        while (queueSize > 0 && sum - dummyHead.next.property.sum >= k) {
            queueSize--
            lastDequeued = dummyHead.deque()
        }

        // Using the lastDequeued value to check
        if (lastDequeued !== undefined) {
            subArraySize = Math.min(subArraySize, i-lastDequeued.property.index)
        }

        // Maintaining the monotonic queue
        while (queueSize > 0 && sum <= dummyTail.prev.property.sum) {
            queueSize--
            dummyTail.pop()
        }

        const newNode = new DoublyLinkedList(sum, i)

        dummyTail.push(newNode)
        queueSize++
    }
    return subArraySize === Number.MAX_SAFE_INTEGER ? -1 : subArraySize
};
Shortest Subarray with Sum at Least K