Minimum Size Subarray Sum

Leetcode Problem 209: Minimum Size Subarray Sum

Problem Summary

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

Constraints:

• The target is a positive integer up to 1,000,000,000.
• The array has between 1 and 100,000 positive integer elements, each up to 10,000.

Techniques

• Array
• Binary Search
• Sliding Window
• Prefix Sum

Solution

function minSubArrayLen(target: number, nums: number[]): number {
    let prefixSum = 0;
    let startSubarray = 0
    let minSubarraySize = nums.length + 1

    for (let i = 0; i < nums.length; i++) {
        prefixSum = prefixSum + nums[i]

        while (prefixSum >= target) {
            minSubarraySize = Math.min(minSubarraySize, i - startSubarray + 1)
            prefixSum = prefixSum - nums[startSubarray]
            startSubarray++
        }
    }

    if (minSubarraySize === nums.length + 1) {
        return 0
    }

    return minSubarraySize
};

console.log(minSubArrayLen(7, [2,3,1,2,4,3]))