892. Shortest Subarray With Sum At Least K¶

Difficulty: Hard

892. Shortest Subarray with Sum at Least K

Hard

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.

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

Constraints:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁹

Solution¶

class Solution {
    static class Pair {
        long key, value;
        public Pair(long key, long value) {
            this.key = key;
            this.value = value;
        }
        @Override
        public String toString() {
            return "(" + key + " " + value + ")";
        }
    }
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        long current_sum = 0;
        Deque<Pair> q = new ArrayDeque<>();
        for (int r = 0; r < n; r++) {
            current_sum += nums[r];
            if (current_sum >= k) res = Math.min(res, r + 1);
            while (!q.isEmpty() && current_sum - q.peekFirst().key >= k) {
                Pair front = q.pollFirst();
                res = (int)(Math.min(res, r - front.value));
            }
            while (!q.isEmpty() && q.peekLast().key > current_sum) q.pollLast();
            q.offerLast(new Pair(current_sum, r));
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here