209. Minimum Size Subarray Sum

Intuition

The goal is to find the minimal length of a subarray whose sum is greater than or equal to the target. We can utilize the sliding window technique to efficiently solve this problem. By maintaining a window that expands and contracts, we can keep track of the sum and update the minimal length dynamically.

Approach

1. Initialize Variables: - min_length to float('inf') to store the minimal length of the subarray found. - sum to 0 to keep track of the sum of the current window. - left to 0 to represent the starting index of the current window.
2. Expand the Window: - Use a for loop to iterate through the array with right representing the end index of the current window. - Add nums[right] to sum to include the current element in the window.
3. Shrink the Window: - Use a while loop to check if sum is greater than or equal to the target. - If true, update min_length with the smaller value between min_length and the current window size (right - left + 1). - Subtract nums[left] from sum and increment left to shrink the window from the left side.
4. Return Result: - After iterating through the array, check if min_length was updated from float('inf'). - If it was, return min_length. Otherwise, return 0, indicating no valid subarray was found.

Complexity

Time Complexity:

O(n), where n is the length of the array. Each element is processed at most twice, once by the right pointer and once by the left pointer.

Space Complexity:

O(1), as the solution only uses a constant amount of extra space for the pointers and variables.

Code

C++

#include 
#include 
using namespace std;
class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int minLen = INT_MAX;
        int right = 0;
        int sum = 0;
        int left = 0;
        while (right < nums.size()) {
            sum += nums[right];
            while (sum >= target) {
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return minLen == INT_MAX ? 0 : minLen;
    }
};

Python

from typing import List
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_length = float('inf')
        right = 0
        sum = 0
        left = 0
        while right < len(nums):
            sum += nums[right]
            while sum >= target:
                min_length = min(min_length, right - left + 1)
                sum -= nums[left]
                left += 1
            right += 1
        return 0 if min_length == float('inf') else min_length

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int right = 0;
        int sum = 0;
        int left = 0;
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

JavaScript

var minSubArrayLen = function (target, nums) {
    let min = Infinity
    let right = 0
    let sum = 0
    let left = 0
    while (right < nums.length) {
        sum += nums[right]
        while (sum >= target) {
            min = Math.min(min, (right - left + 1))
            sum -= nums[left]
            console.log("min", min)
            left++
        }
        right++
    }
    return min == Infinity ? 0 : min
};