Minimum Size Subarray Sum

Find the smallest contiguous subarray whose sum is at least the target.

Open concept page Back to problem map

This is a canonical example of shrinking while a window is valid.

It sharpens the idea that positive numbers make the running sum monotonic enough for sliding windows.

Problem intuition

The brute-force version starts a new sum from every index and checks all possible endings.

The sliding-window solution takes advantage of positive numbers: once the sum is large enough, shrinking from the left is the only way to improve the answer.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Try every start and end

O(n^2)O(1)

Accumulate sums from each start index until you cross the target. Correct, but still quadratic in the worst case.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int best = Integer.MAX_VALUE;

        for (int start = 0; start < nums.length; start++) {
            int sum = 0;

            for (int end = start; end < nums.length; end++) {
                sum += nums[end];

                if (sum >= target) {
                    best = Math.min(best, end - start + 1);
                    break;
                }
            }
        }

        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

Solution 2

Sliding window on positive numbers

O(n)O(1)

Expand right until the sum reaches the target, then shrink left as much as possible while staying valid.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int best = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];

            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return best == Integer.MAX_VALUE ? 0 : best;
    }
}