Minimum Size Subarray Sum

LeetCode 209 | Difficulty: Medium

Medium

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

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

Topics: Array, Binary Search, Sliding Window, Prefix Sum

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 108 ms)

Metric	Value
Runtime	108 ms
Memory	38.7 MB
Date	2022-02-08

Solution

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int sum = 0, result = Int32.MaxValue;
    int i=0;
    for(int j=0;j<nums.Length;j++)
    {
        sum += nums[j];
        while(sum>=target)
        {
            result = Math.Min(result, j-i+1);
            sum -= nums[i];
            i++;
        }    
        
    }
    
    return result ==Int32.MaxValue ? 0 : result;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-15) — 118 ms, 37.6 MB

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int sum = 0, result = Int32.MaxValue;
    int i=0,j=0;
    while(j<nums.Length)
    {
        sum += nums[j++];
        while(sum>=target && i<nums.Length)
        {
            result = Math.Min(result, j-i);
            sum -= nums[i++];           
        }
    }
    
    return result ==Int32.MaxValue ? 0 : result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sliding Window	$O(n)$	$O(k)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Precisely define what the left and right boundaries represent, and the loop invariant.