Given an array of positive integers nums and a positive integer target, return the minimum length of a continuous subarray whose sum is greater than or equal to target.
If no such subarray exists, return 0.
A subarray is a continuous part of the array.
Example 1
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The subarray [4, 3] has sum 7 and length 2. This is the minimum length possible.
Example 2
Input: target = 4, nums = [1, 4, 4]
Output: 1
Explanation: The subarray [4] has sum 4, so the minimum length is 1.
Example 3
Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
Explanation: No subarray has sum greater than or equal to 11.
Brute Force Approach
Every possible subarray can be checked independently. For each range, calculate its sum from scratch and record its length whenever the sum reaches at least target.
This guarantees the answer but repeats many additions across overlapping subarrays.
Algorithm
The size of the array is stored in n. If n is 0, 0 is returned because no subarray can be formed from an empty array.
A variable minLength is initialized with a very large value. This helps us compare and store the smallest valid subarray length found so far.
Two loops are used to generate every possible subarray. The first loop chooses the starting index start, and the second loop chooses the ending index end.
For every subarray from start to end, another loop is used to calculate the sum of all elements inside that range.
If the calculated sum is greater than or equal to target, the current subarray is valid. Its length is calculated as end - start + 1.
minLength is updated only if the current length is smaller than the previous best length. After all subarrays are checked, if minLength is still unchanged, 0 is returned. Otherwise, minLength is returned.
Dry Run
Minimum Size Subarray Sum Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Checks every possible subarray // and calculates its sum from scratch. int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); // No subarray can be formed // from an empty array. if (n == 0) { return 0; } int minLength = INT_MAX; // Choose every possible start. for (int start = 0; start < n; start++) { // Choose every possible end // for the current start. for (int end = start; end < n; end++) { long long currentSum = 0; // Calculate the sum // of the selected range. for (int i = start; i <= end; i++) { currentSum += nums[i]; } // Update the answer when // the current range is valid. if (currentSum >= target) { minLength = min( minLength, end - start + 1 ); } } } // No valid subarray // was found. if (minLength == INT_MAX) { return 0; } return minLength; }};int main() { vector<int> nums = {2, 3, 1, 2, 4, 3}; int target = 7; Solution solution; cout << solution.minSubArrayLen( target, nums ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N³), where N is the size of the array. There are O(N²) possible subarrays, and calculating the sum of each subarray can take O(N) time.
Space Complexity: O(1), because no extra data structure is used. Only a few variables are needed.
Better Approach
Instead of recalculating each range, build the sum while extending end from every start.
Because all values are positive, once a valid range is found for a fixed start, extending it further only increases its length. So the expansion can stop immediately.
Algorithm
The size of the array is stored in n. If n is 0, 0 is returned because there is no subarray to check.
A variable minLength is initialized with a very large value. This stores the smallest valid subarray length found during the process.
The array is traversed using start as the starting index of the subarray. For every start, currentSum is initialized with 0 because a new subarray is being built.
The end pointer moves from start to the end of the array. At every step, nums[end] is added to currentSum. This avoids calculating the sum again from scratch.
If currentSum becomes greater than or equal to target, the subarray from start to end is valid. Its length is calculated as end - start + 1, and minLength is updated if this length is smaller.
After finding the first valid subarray for a fixed start, the loop is stopped. This is safe because all numbers are positive, so adding more elements will only increase the length. After all starting positions are checked, 0 is returned if no valid subarray was found; otherwise, minLength is returned.
Dry Run
Minimum Size Subarray Sum Better Appraoch Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Builds the sum from every start // instead of recalculating each range. int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); // No subarray can be formed // from an empty array. if (n == 0) { return 0; } int minLength = INT_MAX; // Try every possible start. for (int start = 0; start < n; start++) { long long currentSum = 0; // Expand the range // while maintaining its sum. for (int end = start; end < n; end++) { currentSum += nums[end]; // The first valid end gives // the shortest range for this start. if (currentSum >= target) { minLength = min( minLength, end - start + 1 ); break; } } } // No valid subarray // was found. if (minLength == INT_MAX) { return 0; } return minLength; }};int main() { vector<int> nums = {2, 3, 1, 2, 4, 3}; int target = 7; Solution solution; cout << solution.minSubArrayLen( target, nums ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N²), where N is the size of the array. For every starting index, the ending index may move toward the right until the sum becomes greater than or equal to target.
Space Complexity: O(1), because only variables like currentSum and minLength are used.
Optimal Approach
A sliding window avoids restarting from every position. Expand right until the sum reaches target, then move left forward while the window remains valid.
Since all values are positive, removing elements decreases the sum predictably, allowing us to find the smallest valid window for each right boundary in linear time.
Algorithm
The size of the array is stored in n. If n is 0, 0 is returned because no subarray can be formed.
Three variables are initialized: left is set to 0 to mark the left boundary of the window, currentSum is set to 0 to store the sum of the current window, and minLength is set to a very large value to store the smallest valid length.
The right pointer moves from 0 to n - 1. For every nums[right], the element is added to currentSum because it is now included in the current window.
If currentSum becomes greater than or equal to target, the current window is valid. Its length is calculated as right - left + 1, and minLength is updated if this length is smaller.
After updating the answer, nums[left] is removed from currentSum and left is moved one step forward. This shrinking is repeated while currentSum is still greater than or equal to target, because a smaller valid window may still exist.
After the traversal ends, if minLength is still unchanged, it means no valid subarray was found, so 0 is returned. Otherwise, minLength is returned.
Dry Run
Minimum Size Subarray Sum Optimal Appraoch Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Uses a sliding window // to find the shortest valid range. int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); // No subarray can be formed // from an empty array. if (n == 0) { return 0; } int left = 0; long long currentSum = 0; int minLength = INT_MAX; // Expand the window // by moving right forward. for (int right = 0; right < n; right++) { currentSum += nums[right]; // Shrink while the window // still reaches the target. while (currentSum >= target) { minLength = min( minLength, right - left + 1 ); // Remove the leftmost value // to search for a shorter window. currentSum -= nums[left]; left++; } } // No valid subarray // was found. if (minLength == INT_MAX) { return 0; } return minLength; }};int main() { vector<int> nums = {2, 3, 1, 2, 4, 3}; int target = 7; Solution solution; cout << solution.minSubArrayLen( target, nums ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the size of the array. Every element is added once by the right pointer and removed at most once by the left pointer.
Space Complexity: O(1), because only a few variables are used and no extra data structure is required.
FAQs
Q1. Why does the better approach stop after the sum reaches target for one starting index?
Since all numbers are positive, adding more elements will only increase the subarray length. For the same starting index, a longer valid subarray cannot give a smaller answer.
Q2. Why do we return 0 if minLength is unchanged?
If minLength is still unchanged, it means no subarray had sum greater than or equal to target.
Q3. What happens if one element is greater than or equal to target?
The answer becomes 1 because a single element itself forms the smallest possible valid subarray.
Q4. Would this sliding window approach work if negative numbers were also present?
No. This sliding window logic depends on all numbers being positive. With negative numbers, removing or adding elements does not change the sum predictably, so a different approach would be needed.
Be the first to add a comment.