Problem
Given an array of positive integers nums and a positive integer target, return the minimum length of a contiguous subarray whose sum is greater than or equal to target.If no such subarray exists, return 0.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
target = 7
nums = [2,3,1,2,4,3] Output
2 [4,3] Solution
This solution uses the Sliding Window technique. The right pointer expands the window by adding elements until the current sum becomes greater than or equal to the target.Once the condition is satisfied, the left pointer shrinks the window as much as possible while maintaining the required sum.
Each element enters and leaves the window at most once, making the algorithm highly efficient.
For each valid window, the minimum subarray length is updated before shrinking the window further.
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int currentSum = 0;
int minLength = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
currentSum += nums[right];
while (currentSum >= target) {
minLength = Math.min(minLength, right - left + 1);
currentSum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
Complexity
The algorithm processes each element at most twice—once when expanding the window and once when shrinking it. Therefore, the overall time complexity isO(n). The algorithm uses only a few variables regardless of the input size, resulting in a space complexity of
O(1).