862. Shortest Subarray with Sum at Least K #

Problem #

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

Input: A = [2,-1,2], K = 3
Output: 3

Note:

1. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9

Problem Summary #

Return the length of the shortest non-empty contiguous subarray of A whose sum is at least K. If there is no non-empty subarray with sum at least K, return -1.

Notes:

• 1 <= A.length <= 50000
• -10 ^ 5 <= A[i] <= 10 ^ 5
• 1 <= K <= 10 ^ 9

Solution Approach #

• Given an array, find the shortest, non-empty, contiguous subsequence whose cumulative sum is at least k.
• Since the given array may contain negative numbers, the cumulative sum of a subarray will not necessarily increase as the length of the array increases. The problem asks for interval sums, so naturally we need to use the prefixSum prefix sum. First compute the prefixSum prefix sum.
• Simplifying the requirement of the problem, it is whether we can find prefixSum[y] - prefixSum[x] ≥ K, with the difference y - x minimized. If y is fixed, then for x, the larger x is, the smaller the difference y - x is (because x gets closer to y). Therefore, to find the shortest distance of the interval [x, y], we need to ensure that y is as small as possible and x is as large as possible, so that the distance of the interval [x, y] is minimized. Then the following 2 pieces of “common sense” must hold:
  1. If x1 < x2, and prefixSum[x2] ≤ prefixSum[x1], it means the result will definitely not choose x1. Because if prefixSum[x1] ≤ prefixSum[y] - k, then prefixSum[x2] ≤ prefixSum[x1] ≤ prefixSum[y] - k, so x2 can also satisfy the problem requirements, and x2 is closer to y than x1; the optimal solution will definitely consider x2 first.
  2. After x has been determined, there is no need to consider x again later, because if y2 > y1, and when at y2 choosing x is still the same, then when calculating the distance, y2 - x is obviously greater than y1 - x; in this case it definitely will not be the shortest distance.
• From the two pieces of common sense above, we can use a double-ended queue deque to process prefixSum. What is stored in deque are increasing x indices, in order to satisfy the first piece of common sense. Start traversing from the front of the double-ended queue. If the difference of the interval sums is greater than or equal to K, remove the front element and update the result res. Removing elements from the front of the queue until the inequality prefixSum[i]-prefixSum[deque[0]] >= K is no longer satisfied is to satisfy the second piece of common sense. The following loop is the essence of this problem: traverse backward from the end of the double-ended queue. If the current interval sum prefixSum[i] is less than or equal to the interval sum at the end of the queue, remove the element at the end of the queue. Why handle it this way? Because if the array is all positive numbers, then the longer the length, the larger the interval sum must be, so prefixSum[i] must be greater than all interval sums in the double-ended queue. However, because negative numbers may exist, the length may become longer while the total interval sum instead decreases. The previous differences of interval sums were not greater than or equal to K (< K), so the current one is even less likely to be greater than or equal to K; this ending position can be eliminated directly without calculation. After the loop ends, add the current position to the double-ended queue. Removing several elements from the tail when encountering a new index is also to satisfy the first piece of common sense.
• Since every index enters the queue only once and is popped out at most once, the time complexity is O(n), and the space complexity is O(n).

Code #

func shortestSubarray(A []int, K int) int {
	res, prefixSum := len(A)+1, make([]int, len(A)+1)
	for i := 0; i < len(A); i++ {
		prefixSum[i+1] = prefixSum[i] + A[i]
	}
	// deque stores prefixSum indices in increasing order
	deque := []int{}
	for i := range prefixSum {
		// The following loop tries to find a cumulative sum >= K in the interval [deque[0], i]; if found, update the answer
		for len(deque) > 0 && prefixSum[i]-prefixSum[deque[0]] >= K {
			length := i - deque[0]
			if res > length {
				res = length
			}
			// After finding the first deque[0] that satisfies the condition, remove it because it is already the shortest-length subarray
			deque = deque[1:]
		}
		// The following loop ensures that prefixSum[deque[i]] is increasing
		for len(deque) > 0 && prefixSum[i] <= prefixSum[deque[len(deque)-1]] {
			deque = deque[:len(deque)-1]
		}
		deque = append(deque, i)
	}
	if res <= len(A) {
		return res
	}
	return -1
}