862. Shortest Subarray with Sum at Least K

//TC: O(NlogN)
//SC: O(N)
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int length = nums.length;
        long sum=0;
        int res = Integer.MAX_VALUE;

        TreeMap<Long,Integer> map = new TreeMap<>();

        for(int i=0;i<length;i++){
            if(nums[i]>=k) return 1;
            sum+=nums[i];
            if(sum>=k){
                res = Math.min(res,i + 1);
            }

            long remainingSum = sum - k;
            Map.Entry<Long,Integer> entry = map.floorEntry(remainingSum);
            while(entry!=null){
                int index = entry.getValue();
                res = Math.min(res,i - index);
                map.remove(entry.getKey());
                entry = map.floorEntry(entry.getKey()-1);
            }
            map.put(sum,i);
            
        }

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

//TC: O(N)
//SC: O(N)
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long sum=0;
        int res = Integer.MAX_VALUE;

        long[] prefix = new long[n+1];
        for(int i=0;i<n;i++){
            prefix[i+1] = prefix[i] + nums[i];
        }

        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=0;i<n+1;i++){
            //if sum at index i - sum at index at start of dq > =k we remove the start index at dq
            while(!dq.isEmpty() && (prefix[i] - prefix[dq.peekFirst()]) >=k){
                res = Math.min(res,i-dq.pollFirst());
            }    

            //if sum at last in dq >= current sum, we remove the last values from dq
            while(!dq.isEmpty() && prefix[dq.peekLast()]>=prefix[i]){
                dq.pollLast();
            }
            dq.add(i);
        }

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