🎨Now live: Try our Free AI Image Generation Feature

Intuition
The goal is to find the minimal length of a subarray whose sum is greater than or equal to the target. We can utilize the sliding window technique to efficiently solve this problem. By maintaining a window that expands and contracts, we can keep track of the sum and update the minimal length dynamically.
Approach
- Initialize Variables:
-
min_length
tofloat('inf')
to store the minimal length of the subarray found. -sum
to 0 to keep track of the sum of the current window. -left
to 0 to represent the starting index of the current window. - Expand the Window:
- Use a
for
loop to iterate through the array withright
representing the end index of the current window. - Addnums[right]
tosum
to include the current element in the window. - Shrink the Window:
- Use a
while
loop to check ifsum
is greater than or equal to the target. - If true, updatemin_length
with the smaller value betweenmin_length
and the current window size (right - left + 1
). - Subtractnums[left]
fromsum
and incrementleft
to shrink the window from the left side. - Return Result:
- After iterating through the array, check if
min_length
was updated fromfloat('inf')
. - If it was, returnmin_length
. Otherwise, return 0, indicating no valid subarray was found.
Complexity
Time Complexity:
O(n), where n
is the length of the array. Each element is processed at most twice, once by the right
pointer and once by the left
pointer.
Space Complexity:
O(1), as the solution only uses a constant amount of extra space for the pointers and variables.
Code
C++
#include
#include
using namespace std;
class Solution {
public:
int minSubArrayLen(int target, vector& nums) {
int minLen = INT_MAX;
int right = 0;
int sum = 0;
int left = 0;
while (right < nums.size()) {
sum += nums[right];
while (sum >= target) {
minLen = min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return minLen == INT_MAX ? 0 : minLen;
}
};
Python
from typing import List
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = float('inf')
right = 0
sum = 0
left = 0
while right < len(nums):
sum += nums[right]
while sum >= target:
min_length = min(min_length, right - left + 1)
sum -= nums[left]
left += 1
right += 1
return 0 if min_length == float('inf') else min_length
Java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE;
int right = 0;
int sum = 0;
int left = 0;
while (right < nums.length) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
JavaScript
var minSubArrayLen = function (target, nums) {
let min = Infinity
let right = 0
let sum = 0
let left = 0
while (right < nums.length) {
sum += nums[right]
while (sum >= target) {
min = Math.min(min, (right - left + 1))
sum -= nums[left]
console.log("min", min)
left++
}
right++
}
return min == Infinity ? 0 : min
};