Leetcode P209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum.js

/**
 * Problem: Minimum Size Subarray Sum
 * Difficulty: Medium
 * Topics: Array, Binary Search, Sliding Window, Prefix Sum
 *
 * Description:
 * 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.
 *
 * Examples:
 *   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.
 *
 *   Input: target = 4, nums = [1,4,4]
 *   Output: 1
 *
 *   Input: target = 11, nums = [1,1,1,1,1,1,1,1]
 *   Output: 0
 *
 * Approach:
 * The Sliding Window technique is used to maintain an optimal subarray that meets the required sum.
 * - Expand the window by moving the `right` pointer while adding `nums[right]` to `sum`.
 * - Once `sum >= target`, shrink the window from the left until `sum < target`, keeping track of the minimum length.
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */

/**
 * @param {number} target - The target sum.
 * @param {number[]} nums - The array of positive integers.
 * @return {number} - The minimal length of a subarray satisfying the condition.
 */
var minSubArrayLen = function(target, nums) {
    let left = 0, sum = 0, minLength = Infinity;

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];

        // Reduce window size when sum meets or exceeds the target
        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left]; // Shrink window from the left
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
};

// Example usage:
console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // Output: 2
console.log(minSubArrayLen(4, [1,4,4])); // Output: 1
console.log(minSubArrayLen(11, [1,1,1,1,1,1,1,1])); // Output: 0