Minimum Size Subarray Sum #209

Sliding Window Medium

Python Java C++

def minSubArrayLen(s, nums):
    i = 0
    total = 0
    min_len = float('inf')
    
    for j in range(len(nums)):
        total += nums[j]
        
        while total >= s:
            min_len = min(min_len, j - i + 1)
            total -= nums[i]
            i += 1
            
    return min_len if min_len != float('inf') else 0

class Solution {
    // Easy sliding window but algo can get tricky; ensure edge cases are handled
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;

        while (j < nums.length) {
            sum += nums[j];
            
            // Shrink window while sum >= s
            while (sum >= s) {
                min = Math.min(min, j - i + 1);
                sum -= nums[i];
                i++;
            }
            
            j++;
        }
        
        // Return 0 if no valid subarray found
        return min == Integer.MAX_VALUE ? 0 : min;     
    }
}

#include 
#include 
using namespace std;

class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        int i = 0, sum = 0, minLen = INT_MAX;
        
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            
            // Shrink window while sum >= s
            while (sum >= s) {
                minLen = min(minLen, j - i + 1);
                sum -= nums[i];
                i++;
            }
        }
        
        // Return 0 if no valid subarray found
        return minLen == INT_MAX ? 0 : minLen;
    }
};

Problem Statement

Given an array of positive integers `nums` and a positive integer `s`, return the minimal length of a contiguous subarray of which the sum is greater than or equal to `s`. If there isn't one, return `0` instead.

Detailed Explanation

Approach

This solution uses the sliding window technique to dynamically adjust the size of the window and find the smallest subarray that satisfies the condition. The key is to expand the window to meet the condition and then shrink it to find the minimal length.

Key Concepts

1. Sliding Window: Efficiently expands and contracts the window to meet the condition.
2. Window Sum: Tracks the sum of the current window dynamically.

Algorithm Steps

1. Initialize pointers `i` and `j`, a variable `sum` to track the window sum, and `min` to store the smallest valid window size.
2. Expand the window by incrementing `j` and adding `nums[j]` to `sum`.
3. While the condition (`sum >= s`) is met:
   • Update `min` with the smaller of the current value or the window size (`j - i + 1`).
   • Shrink the window by subtracting `nums[i]` from `sum` and incrementing `i`.
4. If no valid subarray is found, return `0`.

Time and Space Complexity

• Time Complexity: O(n)
  • Each element is processed at most twice: once when expanding and once when shrinking the window.
• Space Complexity: O(1)
  • Only a few variables are used for tracking indices and sums.

Why This Works

The solution efficiently adjusts the window size dynamically, minimizing unnecessary operations and ensuring the smallest valid window is found. By maintaining a running sum and shrinking the window only when necessary, we ensure the minimal length is calculated without extra overhead.

Edge Cases

• No valid subarray: Return `0`.
• Single element array: Check if the single element satisfies the condition.
• All elements smaller than `s`: Return `0`.

Common Mistakes

• Not resetting the window correctly when shrinking.
• Returning `Integer.MAX_VALUE` instead of `0` when no valid subarray exists.
• Handling arrays with length less than `k` incorrectly.