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

The time complexity of this code is O(n) and the space complexity of O(n).

Ending Note

This classic sliding window problem is asked during bar raiser and many other online assessments. It is a medium-level problem on LeetCode.