[Leetcode] Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

Given an array of positive integers numsand 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 0instead.

Example 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.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 10``9

1 <= nums.length <= 10``5

1 <= nums[i] <= 10``4

Follow up: If you have figured out the O(n)solution, try coding another solution of which the time complexity is O(n log(n)).

How to approach?

Sliding window

function minSubArrayLen(target: number, nums: number[]): number {
    let min_length = Infinity
    let l = 0;
    let current = 0;

    for (let r = 0; r < nums.length; r++) {
        current += nums[r]
        while (current >= target) {
            min_length = Math.min(min_length, r - l + 1)
            current -= nums[l]
            l++
        }
    }

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

1. set min_length to the Infinity
2. set left pointer at 0, current sum as 0.
3. create for loop using right pointer.
4. add nums' array's right pointer value to the current sum.
5. while current sum is bigger/same than target value, compare the minimum value between min_length and the size of the current window which is r-l+1
6. and pop out the first value from current sum and increment left pointer by 1.
7. while loop will do it while the condition is met.
8. after considering left pointer when the condition doesn't meet, then r pointer will be incremented by 1 and added to the current sum.
9. lastly return the min_length when there is change, if there is no change but still infinite value then return 0, since there is no min_length of the sub array sum is bigger/same than target value.

summary

sliding window technique, use 2 pointers and iterate over the nums array to utilize the current value in subarray and its sum. min_length will be chosed in Math.min comparison.