medium Minimum Size Subarray Sum

Problem Statement

Given a nums array containing positive integers and a positive integer target, return the minimum length of a subarray having the sum of elements greater than or equal to target. If there is no such subarray, return 0 instead.

Examples

Example 1:

• Input: target = 15, nums = [1, 2, 3, 4, 5, 6, 7, 8]
• Expected Output: 2
• Justification: The subarray [7, 8] has a sum of 15, which is equal to target and is the smallest possible subarray.

Example 2:

• Input: target = 11, nums = [2, 1, 5, 2, 8]
• Expected Output: 3
• Justification: The subarray [5, 2, 8] has a sum of 15, which meets the target and is the smallest possible subarray.

Example 3:

• Input: target = 8, nums = [2, 1, 5, 2, 3]
• Expected Output: 3
• Justification: The subarray [5, 2, 3] has a sum of 10, which meets the target and is the smallest possible subarray.

Constraints:

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

Pattern

Variable window — smallest window whose sum ≥ target (positive integers only). Recognition: minimize length subject to an aggregate threshold; elements are positive, so growing the window never decreases the sum and shrinking never increases it (monotonicity). Template: expand end, adding; while sum ≥ target, record length and shrink start. Both pointers advance at most n times → O(n).

When-not: if the array can contain negatives, this shrink logic is wrong (expanding can lower the sum). Switch to prefix sums + binary search on bounds (O(n log n)) or a different technique. Fixed-size "sum of every window of size k" uses the fixed template, not this one.

Edge: no subarray reaches target → return 0. Single element ≥ target → return 1. Empty array is outside constraints here.

Solution

Expand a right pointer while accumulating the window sum. Whenever the sum is at least target, record the window length and shrink from the left as far as the sum stays ≥ target, seeking the shortest valid window. Positivity of the inputs is what makes "shrink while valid" safe and optimal.

Each index is added and removed at most once, so total work is linear.

Step-by-Step Algorithm

1. Initialize Variables:

   • Set start to 0 to denote the start of the sliding window.
   • Set min_length to a large number (e.g., infinity) to keep track of the minimum subarray length found.
   • Set current_sum to 0 to keep track of the sum of the current window.

2. Iterate Through Array:

   • Use a for loop with end ranging from 0 to n-1 (where n is the length of nums).

3. Expand the Window:

   • For each end index, add nums[end] to current_sum.

4. Contract the Window:

   • Use a while loop to check if current_sum is greater than or equal to target.
   • If it is, update min_length to the smaller of min_length and the length of the current window (end - start + 1).
   • Subtract nums[start] from current_sum to reduce the window size.
   • Move the start pointer to the right by incrementing start.

5. Finalize Result:

   • After the loop, check if min_length is still a large number.
   • If it is, return 0 (meaning no valid subarray was found).
   • Otherwise, return min_length.

Algorithm Walkthrough

Using Example 1:

Input: target = 15, nums = [1, 2, 3, 4, 5, 6, 7, 8]

1. Initialize Variables:

   • start = 0
   • min_length = infinity
   • current_sum = 0

2. Iterate Through Array:

   • end = 0: Add nums[0] to current_sum → current_sum = 1

     • current_sum (1) is less than target (15), so do nothing.

   • end = 1: Add nums[1] to current_sum → current_sum = 3

     • current_sum (3) is less than target (15), so do nothing.

   • end = 2: Add nums[2] to current_sum → current_sum = 6

     • current_sum (6) is less than target (15), so do nothing.

   • end = 3: Add nums[3] to current_sum → current_sum = 10

     • current_sum (10) is less than target (15), so do nothing.

   • end = 4: Add nums[4] to current_sum → current_sum = 15

     • current_sum (15) is equal to target (15), so:
       • Update min_length → min_length = min(infinity, 4 - 0 + 1) = 5
       • Subtract nums[start] (1) from current_sum → current_sum = 14
       • Increment start → start = 1

   • end = 5: Add nums[5] to current_sum → current_sum = 20

     • current_sum (20) is greater than target (15), so:
       • Update min_length → min_length = min(5, 5 - 1 + 1) = 5
       • Subtract nums[start] (2) from current_sum → current_sum = 18
       • Increment start → start = 2
     • current_sum (18) is still greater than target (15), so:
       • Update min_length → min_length = min(5, 5 - 2 + 1) = 4
       • Subtract nums[start] (3) from current_sum → current_sum = 15
       • Increment start → start = 3
     • current_sum (15) is equal to target (15), so:
       • Update min_length → min_length = min(4, 5 - 3 + 1) = 3
       • Subtract nums[start] (4) from current_sum → current_sum = 11
       • Increment start → start = 4

   • end = 6: Add nums[6] to current_sum → current_sum = 18

     • current_sum (18) is greater than target (15), so:
       • Update min_length → min_length = min(3, 6 - 4 + 1) = 3
       • Subtract nums[start] (5) from current_sum → current_sum = 13
       • Increment start → start = 5

   • end = 7: Add nums[7] to current_sum → current_sum = 21

     • current_sum (21) is greater than target (15), so:
       • Update min_length → min_length = min(3, 7 - 5 + 1) = 3
       • Subtract nums[start] (6) from current_sum → current_sum = 15
       • Increment start → start = 6
     • current_sum (15) is equal to target (15), so:
       • Update min_length → min_length = min(3, 7 - 6 + 1) = 2
       • Subtract nums[start] (7) from current_sum → current_sum = 8
       • Increment start → start = 7

3. Finalize Result:

   • min_length is 2, which is not infinity.
   • Return min_length, which is 2.

This is the smallest subarray whose sum is at least 15, and it is [7, 8].

Code

class Solution {

  public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int minLength = Integer.MAX_VALUE; // Initialize minLength to a large number
    int currentSum = 0; // To keep track of the current sum
    int start = 0; // Starting index of the sliding window

    for (int end = 0; end < n; end++) {
      currentSum += nums[end]; // Add the current element to currentSum
      while (currentSum >= target) { // While the current sum is greater than or equal to target
        minLength = Math.min(minLength, end - start + 1); // Update minLength
        currentSum -= nums[start]; // Remove the starting element from currentSum
        start++; // Move the starting index to the right
      }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength; // Return 0 if no subarray was found
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[] nums1 = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int[] nums2 = { 2, 1, 5, 2, 8 };
    int[] nums3 = { 2, 1, 5, 2, 3 };
    System.out.println(sol.minSubArrayLen(15, nums1)); // Output: 2
    System.out.println(sol.minSubArrayLen(11, nums2)); // Output: 3
    System.out.println(sol.minSubArrayLen(8, nums3)); // Output: 3
  }
}

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is , where n is the length of the array. This is because each element is processed at most twice, once by the end pointer and once by the start pointer.
• Space Complexity: The space complexity of this algorithm is because we are using a constant amount of extra space regardless of the input size.

🎯 STRICT STANDOUT — Minimum Size Subarray Sum

1. Why / judgment

Minimize length subject to sum ≥ target. With positive nums, sum is monotonic in window growth: expand end; while valid, record length and shrink start. Negatives break monotonicity — switch prefix+binary search.

2. Trace recompute + complexity (K11)

target=15, nums=[1,2,3,4,5,6,7,8]
Expand to end=4 sum=15 → minLen=5; shrink while sum≥15
Continue as page walkthrough; end=7 brings 8 in; shrink to [7,8] → minLen=2 ✓

Pointer accounting: end moves n times; start moves ≤n times; body O(1)
→ total operations ≤ 2n → Θ(n) time, Θ(1) space

If negatives allowed: this while-shrink can miss optima → wrong algorithm.
Prefix sums + binary search lower_bound: Θ(n log n) time, Θ(n) space (prefix).
n=1e5 forbids Θ(n²) double loop.

3. Pattern — VARIABLE WINDOW MIN LENGTH (THRESHOLD SUM) (K12)

Name: Expand/shrink min window sum ≥ target (positives).

Recognition: shortest subarray meeting additive threshold; positive integers.

When-NOT: negatives present → prefix+BS or other; fixed k sum → fixed window; count distinct ≤k → map window.

4. Edge hand-run (K13)

target=100, nums=[1,2,3] → never → 0
target=7, nums=[8] → 1
target=15, [1,2,3,4,5,6,7,8] → 2
target=11, [2,1,5,2,8] → [5,2,8] len 3 ✓

5. Interviewer follow-ups

Q1. Prove O(n).
A: start and end each advance at most n; amortized O(1) per advance.

Q2. Why positives required?
A: Shrinking must never increase sum; expanding must never decrease sum — fails with negatives.

Q3. Return if none?
A: 0 (minLength left at sentinel).