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.

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.

Example 3

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

🏆 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;
};

🔍 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;
};

🔍 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:

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! 🚀