Smallest Subarray With Sum At Least Target

Medium20–25 min

Topics

ArraySliding Window

Companies

AmazonMicrosoftGoogleAdobe

Given an array of positive integers nums and an integer target, find the length of the smallest contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0. Extending a window from every start and checking the sum works, but it re-derives the same ground repeatedly. A sliding window with a variable size does better here: expand the right edge until the sum is enough, then greedily shrink the left edge for as long as it stays enough — every subarray that reaches target gets checked, but each element is added and removed from the running sum at most once, giving O(n) instead of O(n²).

Test Case 1:

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

Output:2

Explanation:The subarray [4, 3] sums to 7 in just 2 elements — no shorter window reaches the target.

Test Case 2:

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

Output:1

Explanation:A single element, 4, already meets the target on its own.

Test Case 3:

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

Output:0

Explanation:The entire array only sums to 8, which never reaches 11 — no valid subarray exists.

Constraints

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 2-12 positive integers (1-20)target — a positive integer

1	class Solution {
2	public int smallestSubarrayWithSumAtLeastTarget(int[] nums, int target) {
3	int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
4	for (int right = 0; right < nums.length; right++) {
5	sum += nums[right];
6	while (sum >= target) {
7	minLen = Math.min(minLen, right - left + 1);
8	sum -= nums[left];
9	left++;
10	}
11	}
12	return minLen == Integer.MAX_VALUE ? 0 : minLen;
13	}
14	}
15

↑left

Variables

left0

sum0

minLeninfinity

INITIALIZE

Start left at 0, sum at 0, and minLen at infinity — no window has been checked yet.

Step 1 / 18

Approach & Solutions

Brute Force

Brute

For every possible starting index, extend the window to the right, accumulating a running sum, until that sum reaches the target — then record the window length and stop extending from this start (going further can only make it longer, never shorter). Correct, but every start re-walks ground a smarter approach could reuse.

TimeO(n²)

SpaceO(1)

Java

Try it out

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

Optimal — Sliding Window

Optimal

Expand a window from the right, accumulating a running sum. The moment that sum reaches the target, the window is valid — but a shorter one might still work, so greedily shrink from the left (subtracting as you go) for as long as the sum stays at or above target, recording the length at every valid point along the way.

TimeO(n)