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


  • 20
    Z

    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;
        }
    }

  • 0
    D

    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;
      }
    }

  • 0

    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
    

  • 0
    O

    Thank you for your clear explanation


Log in to reply
 

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