Untitled

import java.util.Deque;
import java.util.LinkedList;

public class ShortestSubarraySum {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        Deque<Integer> deque = new LinkedList<>();
        int minLength = Integer.MAX_VALUE;

        for (int i = 0; i <= n; i++) {
            // Remove indices from the front where prefix[i] - prefix[deque.front()] >= k
            while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k) {
                minLength = Math.min(minLength, i - deque.pollFirst());
            }

            // Maintain a monotonic increasing deque by removing larger prefix sums from the back
            while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()]) {
                deque.pollLast();
            }

            // Add the current index to the deque
            deque.addLast(i);
        }

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

   
}

public class ShortestSubarraySum {
    public int shortestSubarray(int[] nums, int k) {
        // Deque stores pairs of (index, prefixSum)
        Deque<long[]> deque = new LinkedList<>();
        long prefixSum = 0; // Running prefix sum
        int minLength = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];

            // Check if a valid subarray ending at index i exists
            while (!deque.isEmpty() && prefixSum - deque.peekFirst()[1] >= k) {
                minLength = Math.min(minLength, i - deque.pollFirst()[0] + 1);
            }

            // Maintain monotonicity by removing all elements from the back
            // whose prefix sum is greater than or equal to the current prefix sum
            while (!deque.isEmpty() && prefixSum <= deque.peekLast()[1]) {
                deque.pollLast();
            }

            // Add the current index and prefix sum to the deque
            deque.addLast(new long[]{i, prefixSum});
        }

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