NUHMAN.com

Problem Statement

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

Example

go

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Constraints

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

Approach

We use the Sliding Window technique to achieve O(n) time complexity:

1. Expand the window by moving the right pointer and adding to the sum.
2. Once the sum is ≥ target, shrink the window from the left to find the minimal length.
3. Update the result as the minimal window length whenever the sum is sufficient.

Go Implementation

go

package main

import (
    "fmt"
    "math"
)

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    left, sum := 0, 0
    minLen := math.MaxInt32

    for right := 0; right < n; right++ {
        sum += nums[right]

        for sum >= target {
            minLen = min(minLen, right-left+1)
            sum -= nums[left]
            left++
        }
    }

    if minLen == math.MaxInt32 {
        return 0
    }
    return minLen
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// Example usage
func main() {
    nums := []int{2, 3, 1, 2, 4, 3}
    target := 7
    result := minSubArrayLen(target, nums)
    fmt.Println("Minimum length of subarray:", result) // Output: 2
}

Explanation

• sum: Accumulates the window sum.
• left and right: Define the window.
• When sum ≥ target, we try to shrink the window from the left side to minimize the length.
• Keep track of the smallest window seen that satisfies the condition.

Time and Space Complexity

• Time Complexity: O(n), since each element is processed at most twice.
• Space Complexity: O(1), constant space.

Conclusion

This problem is a textbook example of using a sliding window to optimize subarray problems. It's efficient and elegant, especially compared to the brute-force O(n²) approach.