Problem

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.

Examples

Example 1:

1
2

Input: nums = [1], k = 1
Output: 1

Example 2:

1
2

Input: nums = [1,2], k = 4
Output: -1

Example 3:

1
2

Input: nums = [2,-1,2], k = 3
Output: 3

Solution

Method 1 - Prefix sum + Monotonic queue

  1. Prefix Sum and Monotonic Queue:
    • We use a prefix sum array to keep track of cumulative sums.
    • A deque (double-ended queue) is used to maintain indices of the prefix sum array in increasing order.
    • For each index i, while there are indices in the deque and the prefix sum difference between the current index and the front of the deque is at least K, we update the minimum length.
    • We maintain the deque such that it helps to find the smallest subarray with the required sum efficiently.
  2. Steps:
    • Initialise a deque and the prefix sum array.
    • Traverse the prefix sum array.
    • For each element, ensure that the elements in the deque are increasing.
    • Calculate the potential minimum length whenever the required sum condition is met.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

        Deque<Integer> dq = new LinkedList<>();
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < prefixSum.length; i++) {
            while (!dq.isEmpty() && prefixSum[i] - prefixSum[dq.peekFirst()] >= k) {
                ans = Math.min(ans, i - dq.pollFirst());
            }
            while (!dq.isEmpty() && prefixSum[i] <= prefixSum[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.addLast(i);
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]

        dq = deque()
        ans = float('inf')

        for i in range(len(prefix_sum)):
            while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
                ans = min(ans, i - dq.popleft())
            while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
                dq.pop()
            dq.append(i)

        return ans if ans != float('inf') else -1

Complexity

  • ⏰ Time complexity: O(n) because each element is processed at most twice (once added and once removed from the deque).
  • 🧺 Space complexity: O(n),  due to the extra space used for the prefix sum array and the deque.