Minimum Size Subarray Sum

Introduction

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.

// 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

Solution

There can be multiple solutions for this problem but I am going to discuss 2 leading solutions i.e Brute Force and Sliding Window Algorithm

const minSubArrayLen = (nums, target) => {
    let n = nums.length;
    let min = Infinity;

    for (let i = 0; i < n; i++) {
        let sum = 0;
        for (let j = i; j < n; j++) {
            sum += nums[j];
            if (sum >= target) {
                min = Math.min(min, j - i + 1);
                break;
            }
        }
    }

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

const target = 7, nums = [2, 3, 1, 2, 4, 3]
const res = minSubArrayLen(nums, target)
console.log(res) //2

The time complexity of this code is O(n^2) and the space complexity of O(1).
Note - This approach will fail in leetcode

Sliding Window

const minSubArrayLen = (nums, target) => {
    let ans = Infinity, left = 0, window = 0, n = nums.length;

    for (let right = 0; right < n; right++) {

        window += nums[right];

        while (window >= target) {
            let windowLength = (right - left) + 1
            ans = Math.min(ans, windowLength)
            window -= nums[left]
            left++
        }

    }


    if (ans === Infinity) {
        ans = 0
    }
    return ans
}

const target = 7, nums = [2, 3, 1, 2, 4, 3]
const res = minSubArrayLen(nums, target)
console.log(res) //2