DEV Community

Cover image for LeetCode Challenge: 209. Minimum Size Subarray Sum - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on β€’ Edited on

1 1 1 1 1

LeetCode Challenge: 209. Minimum Size Subarray Sum - JavaScript Solution πŸš€

Top Interview 150

The Minimum Size Subarray Sum problem is an excellent example of sliding window and binary search techniques. Let’s tackle this problem and explore both O(n) and O(nlogn) solutions.


πŸš€ Problem 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 no such subarray exists, return 0.

πŸ’‘ Examples

Example 1

Input: target = 7, nums = [2,3,1,2,4,3]  
Output: 2  
Explanation: The subarray `[4,3]` has a sum of 7, which is the minimal length.
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: target = 4, nums = [1,4,4]  
Output: 1  
Explanation: The subarray `[4]` has a sum of 4, which is the minimal length.
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: target = 11, nums = [1,1,1,1,1,1,1,1]  
Output: 0  
Explanation: No subarray meets the condition.
Enter fullscreen mode Exit fullscreen mode

πŸ† JavaScript Solutions

Approach 1: Sliding Window (O(n))

The sliding window technique allows us to dynamically adjust the window size as we traverse the array.

Implementation

var minSubArrayLen = function(target, nums) {
    let left = 0;
    let sum = 0;
    let minLength = Infinity;

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

        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” How It Works

  1. Expand the Window:

    • Add elements to the sum by moving the right pointer.
  2. Shrink the Window:

    • When the sum becomes greater than or equal to target, update the minLength and shrink the window by moving the left pointer.
  3. Edge Case:

    • If no subarray meets the condition, return 0.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array.
    • Each element is processed at most twice (once by right and once by left).
  • Space Complexity: O(1), as we use constant extra space.

Approach 2: Binary Search (O(nlogn))
An alternative approach uses binary search to find the minimal subarray for each possible starting point.

Implementation

var minSubArrayLen = function(target, nums) {
    const n = nums.length;
    const prefixSum = Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
    }

    let minLength = Infinity;

    for (let i = 0; i < n; i++) {
        const desiredSum = prefixSum[i] + target;
        let left = i + 1, right = n;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (prefixSum[mid] >= desiredSum) {
                minLength = Math.min(minLength, mid - i);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }

    return minLength === Infinity ? 0 : minLength;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” How It Works

  1. Prefix Sum:

    • Compute a prefix sum array where prefixSum[i] is the sum of the first i elements.
  2. Binary Search:

    • For each starting index i, find the smallest ending index j such that prefixSum[j] - prefixSum[i] >= target.
  3. Update Result:

    • Update minLength with the smallest valid subarray length.

Complexity Analysis

  • Time Complexity: O(nlogn), due to the binary search for each starting index.
  • Space Complexity: O(n), for the prefix sum array.

πŸ“‹ Dry Run

Input: target = 7, nums = [2,3,1,2,4,3]

Sliding Window Steps:
Dry Run
Output: 2


✨ Pro Tips for Interviews

  1. Explain Sliding Window: Highlight its efficiency in adjusting window size dynamically.
  2. Discuss Edge Cases:

    • nums with a single element equal to target.
    • Subarrays with all elements smaller than target.
  3. Follow-Up: Mention how binary search is an alternative if asked for optimization.


πŸ“š Learn More

Check out the previous full explanation and code walkthrough on my Dev.to post:
πŸ‘‰ 3Sum - JavaScript Solution

Which approach would you use? Let’s discuss below! πŸš€


Keep Studying

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (2)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal β€’

Follow Me on GitHub πŸš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Collapse
 
betterslip profile image
BetterSlip β€’

Nice!

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay