https://leetcode.com/problems/minimum-size-subarray-sum/

My solution:

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    ans := n + 1
    sums := make([]int, n+1)
    for i:=1; i<n+1; i++ {
        sums[i] = sums[i-1] + nums[i-1]
    }
    
    for i:=1; i<n+1; i++ {
        toFind := sums[i-1] + target
        bound := lowerBound(sums, toFind, i)
        if bound != -1 {
            ans = min(ans, bound - i + 1)
        }
    }
    if ans == n+1 {
        return 0
    }
    return ans
}

func lowerBound(nums []int, target int, lowStart int) int {
    low, high := lowStart, len(nums)-1
    for low <= high {
        mid := low + (high-low)>>1
        if nums[mid] < target {
            low = mid + 1
        } else {
            if mid == 0 || nums[mid-1] < target {
                return mid
            } else {
                high = mid - 1
            }
        }
    }
    return -1
}

This question is similar to https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/submissions/ except we can only have positive integers in this question while the other can have negative number. The solution assumes the prefix sum array (sums) is strictly increasing. This is a key assumption for the binary search approach used in the lowerBound function to work correctly. But the assumption breaks in the other problem.

The test case [44,-25,75,-50,-38,-42,-32,-6,-40,-47] with target 19 is a good example where my solution fails. My method might skip some valid subarrays that meet the condition.

Here’s an approach using a deque (double-ended queue) to efficiently find the shortest subarray for https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/submissions/:

  1. Use a deque to store indices of the sums array. The deque will help in efficiently finding the minimum length subarray.
  2. Iterate through the array while maintaining the prefix sums.
  3. For each new prefix sum, pop elements from the back of the deque if they are greater than or equal to the current prefix sum. This is because such elements will not contribute to a shorter subarray.
  4. Check if the front of the deque can form a valid subarray that meets or exceeds the target sum. If so, update the answer accordingly and pop it from the front.
  5. Add the current index to the deque.

This approach ensures that the deque always has indices in increasing order of their corresponding prefix sums, and it effectively finds the shortest subarray that meets the condition.

Why do we need an increasing order of their prefix sums? When the prefix sum at the current index (let’s call it sum[i]) is less than or equal to the prefix sum at the back of the deque (say sum[dequeBack]), it indicates that the subarray from dequeBack to i has a non-positive sum (could be zero or negative). Adding the segment from dequeBack to i doesn’t increase the sum. In fact, it could potentially decrease the sum or keep it the same.

func shortestSubarray(nums []int, k int) int {
    n := len(nums)
    deque := []int{}
    
    sums := make([]int, n+1)
    for i:=0; i<n; i++ {
        sums[i+1] = sums[i] + nums[i]
    }
    
    ans := n+1
    
    for i:=0; i<n+1; i++ {
        for len(deque) > 0 && sums[i] - sums[deque[0]] >= k {
            // subarray [deque[0]+1, I]
            ans = min(ans, i-deque[0])
            deque = deque[1:]
        }
        
        for len(deque) > 0 && sums[i] <= sums[deque[len(deque)-1]] {
            deque = deque[:len(deque)-1]
        }
        
        deque = append(deque, i)
    }
    
    if ans == n+1 {
        return -1
    }
    
    return ans
}