Minimum Size Subarray Sum — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Minimum Size Subarray Sum problem optimally.
O(n)O(1)Problem Description
Given an array of positive integers nums and an integer target, determine the length of the shortest contiguous subarray whose sum is at least target. If no such subarray exists, return 0.
The input array nums contains only strictly positive integers. You must find the minimum number of consecutive elements required to meet or exceed the specified target value. The solution should be efficient, avoiding brute-force checks of all possible subarrays.
Return the minimum length of the subarray satisfying the condition. If the sum of the entire array is less than target, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Size Subarray Sum"
WHY DOES IT MATTER?
Sliding‑window patterns are fundamental for any problem that asks for optimal sub‑structures over contiguous sequences, especially when the input is large and the operation (like sum) can be updated incrementally.
OPTIMIZATION CHALLENGE
The key insight is recognizing that with all positive numbers the window sum only grows when extending to the right, enabling a greedy shrink from the left as soon as the condition is met, which collapses the quadratic search space to linear.
REAL-WORLD CONNECTION
Think of a network traffic monitor that continuously aggregates bytes over a moving time window; it must quickly adjust the window as new packets arrive and old ones expire, mirroring the left‑right pointer adjustments in this algorithm.
During an interview, write the two‑pointer skeleton first, then immediately add the inner while‑loop that contracts the window; this shows you understand both expansion and contraction phases and avoids off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The Minimum Size Subarray Sum problem is a classic sliding‑window scenario where we need to find the smallest contiguous segment whose sum meets a threshold. A naïve solution enumerates every possible subarray, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n = 10⁵) because each additional element multiplies the number of checks. The optimal paradigm leverages the monotonic growth of the sum when all numbers are positive: expanding the right boundary never decreases the current sum, allowing us to shrink the left boundary greedily once the sum reaches or exceeds the target. This two‑pointer (or sliding‑window) technique maintains a running sum and dynamically adjusts the window size, guaranteeing a linear pass through the array while preserving correctness.
Because the array contains only positive integers, the window’s sum is a strictly increasing function of its right edge. When the sum is sufficient, moving the left edge forward can only reduce the sum, potentially invalidating the condition and prompting further expansion. This property eliminates the need for backtracking or recomputation of sums, which is why the sliding‑window approach achieves O(n) time and O(1) auxiliary space, the optimal bounds for this problem.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain zero or negative numbers?
The sliding‑window technique relies on monotonic increase of the sum, which fails with non‑positive values. In that case you would need a different approach, such as prefix sums combined with a balanced binary search tree (or deque) to query the smallest prefix index that satisfies prefix[j] - prefix[i] >= target, yielding O(n log n) time.
Q2Can you solve the problem in O(n) time without using extra space beyond a few variables?
Yes. Use two pointers (left and right) and a running sum. Increment right to grow the window, and whenever the sum >= target, update the answer with the window length and move left forward while subtracting nums[left] to try a smaller window. This maintains O(1) extra space.
Q3What is the worst‑case scenario for the sliding‑window algorithm, and how does it affect runtime?
The worst case occurs when the target is larger than the sum of the entire array, causing the right pointer to traverse the whole array once and the left pointer never moves. Even then each element is visited at most twice (once by right, once by left), so the total operations remain linear, O(n).
Examples
Input
nums = [2, 3, 1, 2, 4, 3], target = 7
Output
2
Explanation: The subarray [4, 3] has a sum of 7, which meets the target. Its length is 2. No subarray of length 1 has a sum >= 7 (max element is 4). Thus, the minimum length is 2.
Input
nums = [1, 4, 4], target = 4
Output
1
Explanation: The element 4 at index 1 has a sum of 4, which meets the target. Its length is 1. This is the minimum possible length for any non-empty subarray.
Input
nums = [1, 1, 1, 1], target = 5
Output
0
Explanation: The sum of the entire array is 4, which is less than the target 5. Therefore, no subarray exists that satisfies the condition, and the result is 0.
Input
nums = [5, 1, 3, 2], target = 6
Output
2
Explanation: The subarray [5, 1] has a sum of 6, meeting the target with length 2. The subarray [3, 2] has a sum of 5, which is insufficient. No single element is >= 6. Thus, the minimum length is 2.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
- 1 <= target <= 10^9
Optimal Approach & Strategy
Maintain two pointers defining a window and a running sum; move the right pointer to increase the sum, and when the sum is ≥ target, move the left pointer to shrink the window while updating the answer. This yields a linear O(n) solution with O(1) extra space.
Brute Force Approach
Enumerate every possible start index, then for each start sum successive elements until the sum reaches the target or the array ends, tracking the smallest length found. This requires nested loops and runs in O(n²) time.
Step-by-Step Dry Run
Input: target = 7, nums = [2,3,1,2,4,3] Right = 0: sum = 2 Right = 1: sum = 5 Right = 2: sum = 6 Right = 3: sum = 8 >= 7 -> minLen = 4, shrink left -> sum = 6 Right = 4: sum = 10 >= 7 -> minLen = 4, shrink left -> sum = 7 >= 7 -> minLen = 3, shrink left -> sum = 6 Right = 5: sum = 9 >= 7 -> shrink left -> minLen = 2, shrink left -> sum = 3. Result: 2
Code Solutions
function minSubArrayLen(nums, target) {
let left = 0, currSum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = Math.min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen === Infinity ? 0 : minLen;
}class Solution {
public:
int minSubArrayLen(vector<int>& nums, int target) {
int left = 0, currSum = 0, minLen = INT_MAX;
for (int right = 0; right < nums.size(); right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}
};class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, currSum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = Math.min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}def minSubArrayLen(nums, target):
left, curr_sum, min_len = 0, 0, float('inf')
for right in range(len(nums)):
curr_sum += nums[right]
while curr_sum >= target:
min_len = min(min_len, right - left + 1)
curr_sum -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_lenfunction minSubArrayLen(nums, target) {
let left = 0, currSum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = Math.min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen === Infinity ? 0 : minLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.