Minimum Size Subarray Sum

Photo by Mohammad Rahmani on Unsplash

When I first read this problem, the requirement looked simple: Find the smallest length of a contiguous subarray whose sum is greater than or equal to target.

But the key word here is contiguous.
That immediately tells us this is likely a sliding window problem.

Understanding the Problem

We are given:

• A positive integer target
• An array of positive integers nums

We must:

• Find the minimum length of a subarray
• Such that its sum ≥ target
• If no such subarray exists, return 0

Example

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

Possible valid subarrays:

• [2,3,1,2] → sum = 8 (length 4)
• [3,1,2,4] → sum = 10 (length 4)
• [2,4,3] → sum = 9 (length 3)
• [4,3] → sum = 7 (length 2) ← smallest

Answer: 2

First Thought (Brute Force Approach)

The most straightforward idea:

• Start from every index
• Keep adding elements
• Stop when sum ≥ target
• Track minimum length

Brute Force Code

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Why This Is Not Optimal

Time complexity:

• O(n²)
• Nested loops

For large arrays, this will be too slow.

Key Observation

All numbers are positive.

This changes everything.

Get Anish More’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Because numbers are positive:

• If we increase the window size → sum increases
• If we shrink the window → sum decreases

This monotonic behavior allows us to use the sliding window technique.

Optimized Approach: Sliding Window

Core Idea

We maintain:

• i → left pointer
• j → right pointer
• sum → current window sum

Process:

1. Expand the window by moving j
2. Add nums[j] to sum
3. Once sum ≥ target:

• Update minimum length
• Shrink window from the left (i++)
• Keep shrinking while sum ≥ target

This guarantees we always try to minimize the window.

Approach (Explained Clearly)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0, j = 0;
        int sum = 0;
        int len = nums.length;
        int minLen = len + 1;
         while (j < len) {
            sum += nums[j];
            while (sum >= target) {
                minLen = Math.min(minLen, j - i + 1);
                sum -= nums[i];
                i++;
            }
            j++;
        }
        return minLen == len + 1 ? 0 : minLen;
    }
}

Why This Works

Because all numbers are positive:

• Expanding window → increases sum
• Shrinking window → decreases sum

So once sum ≥ target:

• Any further expansion would only increase length
• So we shrink immediately to find smallest valid window

This greedy shrinking ensures minimum length.

Step-by-Step Example

Input:

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

Minimum length found: 2

Time and Space Complexity

Brute Force

Sliding Window (Optimized)

Why O(n)?

• Each element is visited at most twice:
• Once by j
• Once by i

So total operations are linear.

Comparison Table

Why Sliding Window Works Only Here

Sliding window works because:

• All numbers are positive
• Sum changes predictably

If negative numbers were allowed:

• Shrinking window might increase sum
• Expanding window might decrease sum
• Sliding window would fail

That’s why constraints matter.

Final Takeaway

This problem is a classic sliding window example.

Whenever you see:

• Contiguous subarray
• Positive integers
• Condition on sum

Immediately think:

Can I use a dynamic window that expands and shrinks.

The transition from O(n²) brute force to O(n) sliding window is not just optimization — it’s pattern recognition.

Once you recognize this pattern, many similar problems become straightforward.