# 1 ms O(n) time solution in Java - dynamic sliding window

• We will maintain a window that grows until sum reach the given sum. Once the window grows to sum at least s then we can start shirking the window from left with the hope to find a smaller window. We shrink until sum falls below s. Then we can grow the window on right again and so on. We keep this procedure of growing-shrinking until the window start reaches the end of the array. Below is the implementation of the above idea which runs in O(n) time and O(1) space.

``````public class Solution {
public int minSubArrayLen(int sum, int[] nums) {
int minlen = Integer.MAX_VALUE;
int curSum = 0;
int start = 0;
int end = 0;

while(start < nums.length){
//if current window doesn't add up to the given sum then
//strech the window to right
if(curSum < sum && end < nums.length){
curSum += nums[end];
end++;
}
//if current window adds up to at least given sum then
//we can shrink the window
else if(curSum >= sum){
minlen = Math.min(minlen, end-start);
curSum -= nums[start];
start++;
}
//cur sum less than required sum but we reach the end
else{
break;
}
}

return (minlen == Integer.MAX_VALUE) ? 0 : minlen;
}
}``````

• A very extreme case if the array is [1,....,1] and array length is Integer.MAX_VALUE you answer would return 0 while Integer.MAX_VALUE is expected. A little change in the code:

``````public class Solution {
public int minSubArrayLen(int sum, int[] nums) {
int minlen = 0;
int curSum = 0;
int start = 0;
int end = 0;

while(start < nums.length){
//if current window doesn't add up to the given sum then
//strech the window to right
if(curSum < sum && end < nums.length){
curSum += nums[end];
end++;
}
//if current window adds up to at least given sum then
//we can shrink the window
else if(curSum >= sum){
minLen = (minLen == 0 || minLen > end - start) ? end-start : minLen;
curSum -= nums[start];
start++;
}
//cur sum less than required sum but we reach the end
else{
break;
}
}

return minlen;
}
}``````

• Thank you! Here is a python version of this solution!

``````class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
minlen  = 2**31-1
start = 0
end = 0
cursum = 0
while start<len(nums):
if cursum<s and end<len(nums):
cursum+= nums[end]
end +=1
elif cursum>=s:
minlen = min(minlen, end-start)
cursum-= nums[start]
start+=1
else: #when cursum <s but reach the end
break
if minlen==2**31-1:
return 0
else:
return minlen
``````

• Thank you for your clear explanation

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.