Minimum Size Subarray Sum

Problem Statement

Given an array of positive integers nums and a positive integer target, the goal is to 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.

Examples

1. 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.
2. Input: target = 4, nums = [1, 4, 4] Output: 1 Explanation: The subarray [4] has the minimal length.
3. Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1] Output: 0 Explanation: There is no subarray whose sum is greater than or equal to 11.

Solution Explanation

Approach

To solve this problem, we can use the sliding window technique. The sliding window technique involves maintaining a window of elements that satisfies certain conditions and adjusting the window’s size and position to find the optimal solution.

Steps

1. Initialize Variables:

• minWindowLen to store the minimum length of the subarray found. Initialize it to Int.MAX_VALUE.
• currentSum to keep track of the sum of the current window. Initialize it to 0.
• Two pointers low and high to represent the bounds of the window. Both are initialized to 0.

2. Expand the Window:

• Use a while loop to expand the window by moving the high pointer from the beginning to the end of the array (nums.size).
• Add nums[high] to currentSum and increment high.

3. Contract the Window:

• Use a nested while loop to check if the currentSum is greater than or equal to target.
• If true, calculate the current window length (high - low).
• Update minWindowLen with the minimum value between the current window length and minWindowLen.
• Subtract nums[low] from currentSum and increment low.

4. Return Result:

• After processing the entire array, check if minWindowLen was updated from its initial value. If it was, return minWindowLen. Otherwise, return 0.

Code

Here is the Kotlin implementation of the solution:

fun main() {
    val nums = intArrayOf(2, 3, 1, 2, 4, 3)
    val target = 7
println("result -> ${minSubarraySum(target, nums)}")
}
fun minSubarraySum(target: Int, nums: IntArray): Int {
    var minWindowLen = Int.MAX_VALUE
    var currentSum = 0
    var low = 0
    var high = 0
    while (high < nums.size) {
        currentSum += nums[high]
        high++
        while (currentSum >= target) {
            val currentWindowLen = high - low
            minWindowLen = kotlin.math.min(currentWindowLen, minWindowLen)
            currentSum -= nums[low]
            low++
        }
    }
    return if (minWindowLen == Int.MAX_VALUE) 0 else minWindowLen
}

Time and Space Complexity

• Time Complexity: O(n)
• Each element in the array is processed at most twice (once by the high pointer and once by the low pointer), making the algorithm linear in terms of time complexity.
• Space Complexity: O(1)
• The algorithm uses a constant amount of extra space, as it only uses a few variables (minWindowLen, currentSum, low, high) regardless of the size of the input array.

This solution efficiently finds the minimal length subarray with a sum greater than or equal to the target using a sliding window approach.

For the complete implementation, you can refer to the code in this GitHub repository.