Introduction

The Minimum Size Subarray Sum problem asks us to find the shortest contiguous subarray whose sum is at least a given target.

Given an array of positive integers and a target value, the task is to find the minimum length of a contiguous subarray whose sum is greater than or equal to the target.

This problem helps in understanding:

  • Subarrays
  • Sliding Window
  • Two Pointer Technique
  • Dynamic window size

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimum length of a contiguous subarray whose sum is greater than or equal to target.

If no such subarray exists, return 0.

Example

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

Output:
2

Explanation:
The subarray [4, 3] has a sum of 7.
Its length is 2, which is the minimum possible length.

Input:target = 4
nums = [1, 4, 4]

Output:
1

Explanation:
The single element [4] has a sum equal to the target.
Therefore, the minimum length is 1.

Constraints

  • 1 ≤ target ≤ 10⁹
  • 1 ≤ nums.length ≤ 10⁵
  • 1 ≤ nums[i] ≤ 10⁴

Approach 1: Brute Force

Explanation

The brute force approach considers every possible starting position and calculates the sum of the subarray by expanding toward the right.

Whenever the sum becomes greater than or equal to target, update the minimum length.

Steps

  1. Start from every index.
  2. Initialize the current sum to 0.
  3. Expand the subarray toward the right.
  4. Add each element to the current sum.
  5. When the sum reaches the target, update the minimum length.
  6. Continue until all possible starting positions are checked.

Dry Run

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

Start at index 0:
2 → sum = 2
2 + 3 → sum = 5
2 + 3 + 1 → sum = 6
2 + 3 + 1 + 2 → sum = 8
Length = 4
Minimum = 4

Start at index 1:
3 → sum = 3
3 + 1 → sum = 4
3 + 1 + 2 → sum = 6
3 + 1 + 2 + 4 → sum = 10
Length = 4

Start at index 2:
1 + 2 + 4 = 7
Length = 3
Minimum = 3

Start at index 4:
4 + 3 = 7
Length = 2
Minimum = 2

Final Result:
2

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)

In the worst case, every starting position may scan the remaining elements.

Space Complexity: O(1)

Only a constant amount of extra space is used.

Approach 2: Optimized Solution

Explanation

The optimized approach uses the Sliding Window Technique.

Maintain a window using two pointers:

  • left points to the beginning of the window.
  • right expands the window.

When the sum becomes greater than or equal to target, we try to shrink the window from the left while keeping the sum valid.

Because all numbers are positive, removing elements from the left always decreases the sum, making the sliding window approach possible.

Steps

  1. Initialize left = 0, sum = 0, and minLength = infinity.
  2. Move right through the array.
  3. Add the current element to sum.
  4. While sum ≥ target:
    • Update the minimum length.
    • Remove nums[left] from the sum.
    • Move left forward.
  5. Return the minimum length.
  6. If no valid subarray exists, return 0.

Dry Run

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

Start:
left = 0
sum = 0
minimum = infinity

Add 2:
sum = 2

Add 3:
sum = 5

Add 1:
sum = 6

Add 2:
sum = 8
Window = [2, 3, 1, 2]
minimum = 4

Remove 2:
sum = 6
left = 1

Add 4:
sum = 10
Window = [3, 1, 2, 4]
minimum = 4

Remove 3:
sum = 7
Window = [1, 2, 4]
minimum = 3

Remove 1:
sum = 6
left = 2

Add 3:
sum = 9
Window = [2, 4, 3]
minimum = 3

Remove 2:
sum = 7
Window = [4, 3]
minimum = 2

Remove 4:
sum = 3

Final Result:
2

Optimized Code

Complexity Analysis

Time Complexity: O(n)

Each element is added to the window once and removed from the window at most once.

Space Complexity: O(1)

Only a constant number of variables are used.

Edge Cases

  1. No valid subarray: Return 0.
  2. Single element reaches target: Return 1.
  3. Entire array is required: Return the array length.
  4. Target is larger than the total sum: Return 0.
  5. Multiple valid subarrays: Return the shortest one.

Why This Problem is Important

This problem helps in understanding:

  1. Sliding Window
  2. Two Pointer Technique
  3. Variable-size windows
  4. Subarray problems
  5. Optimization from O(n²) to O(n)

Real-World Applications

Sliding window techniques can be useful in:

  1. Network traffic analysis
  2. Financial data analysis
  3. Continuous monitoring
  4. Log processing
  5. Real-time data streams

Common Mistakes

  1. Forgetting that the array contains positive integers.
  2. Not shrinking the window after reaching the target.
  3. Updating the minimum length at the wrong time.
  4. Forgetting to remove nums[left] from the sum.
  5. Returning infinity instead of 0 when no valid subarray exists.

Interview Tips

The key observation is that all elements are positive.

Once the window sum reaches the target, try to shrink the window from the left to find a smaller valid subarray.

The important condition is:

While sum ≥ target, shrink the window.

Related Questions

  1. Maximum Consecutive Ones
  2. Maximum Consecutive Ones III
  3. Maximum Average Subarray I
  4. Number of Sub-arrays of Size K and Average ≥ Threshold
  5. Subarray Sum Equals K

Final Takeaway

The Minimum Size Subarray Sum problem is a classic variable-size Sliding Window problem.

The brute force approach checks multiple subarrays, while the optimized approach expands and shrinks a single window to achieve O(n) time and O(1) extra space.