Problem List

Minimum Size Subarray Sum

May 31, 2025 • Go • array, sliding window, prefix sum • medium

Problem

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Approach

1. Create sliding window starting at [0,0]
2. Expand the window by moving the right pointer while the sum is less than the target
3. Once the sum becomes ≥ target, attempt to shrink the window by moving the left pointer to find a smaller valid subarray
4. Track the minimal length of all valid windows
5. Repeat until the right pointer reaches the end of the array
6. This approach ensures the entire array is only scanned once, giving linear time complexity
7. Example: (target = 7, nums = [2,3,4,1,2,4,3]):
8. - window grows: [2], [2,3], [2,3,1], [2,3,1,2]
9. - window meets/exceeds target: [2,3,1,2] → try to shrink
10. - shrink and re-expand as needed
11. - find shorter valid subarrays like [1,2,4] and [4,3]

Reflections

This problem reinforced the power of the sliding window technique when dealing with contiguous subarrays and sum conditions. In retrospect, I overcomplicated earlier attempts by creating new slices for every window—using an integer variable to track the sum inline is way more efficient.

Performance

Runtime beats: 100%
Memory beats: 95%

Complexity

Time: O(n)
Space: O(1)

Go Solution

func minSubArrayLen(target int, nums []int) int {
    left, right := 0,0
    n := len(nums)
    candidate := 0
    sum := 0

    for right <= n {
        window := nums[left:right]

        if sum < target {
            if right <= n - 1{
                sum += nums[right]
            }
            right++
        } else if sum >= target {
            candidate = getCandidate(candidate,len(window))
            sum -= nums[left]
            left++
        }
    }

    return candidate
}

func getCandidate(a, b int) int {
    if a == 0 {
        return b
    }

    if a < b {
        return a
    } 

    return b
}

LeetCode Problem Link