Stack, Queue and Deque Problems

Stack, Queue, and Deque Problems | Also see:- Bit Manipulation and Math DSA Problems, Array DSA Problems, Binary Search DSA Problems, Sliding Windows and Two Pointers

Table of Contents

• 1. Shortest Subarray with Sum at Least K

1. 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. Problem: 862

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length, res = Integer.MAX_VALUE;
        long[] prefixSum = new long[n+1];
        for(int i=0; i<n; i++){
            prefixSum[i+1] = prefixSum[i] + nums[i];
        }
        Deque<Integer> deque = new LinkedList<>();
        for(int i=0; i<=n; i++){
            while(!deque.isEmpty() && prefixSum[i] - prefixSum[deque.peekFirst()] >= k){
                res = Math.min(res, i - deque.pollFirst());
            }
            while(!deque.isEmpty() && prefixSum[i] <= prefixSum[deque.peekLast()]){
                deque.pollLast();
            }
            deque.addLast(i);
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!