Minimum Size Subarray Sum

Patrick Leaton
Published: June 20, 2021, 11:30 a.m.
Problem Description

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

 

Constraints:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

 

The description was taken from https://leetcode.com/problems/minimum-size-subarray-sum/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums or len(nums) == 0:
            return 0
        left, right = 0, 0
        min_size, current_sum = float('inf'), 0
        while right < len(nums):
            current_sum += nums[right]
            while current_sum >= target:
                min_size = min(min_size, right-left+1)
                current_sum -= nums[left]
                left += 1
            right += 1
        if min_size != float('inf'):
            return min_size
        else:
            return 0

Problem Explanation

Within the input array, there exists a subarray that contains each valid answer.  In order to get that answer, we can use two pointers which we will slide around and look at various subarrays.

We can achieve this by utilizing a sliding window.  A good indication that this is the right approach is when the input is a string or some type of list, and we are asked to return something like the "longest', "maximum", "minimum", or a condition similar to that.  

Like other sliding window problems, we will have a running count, we will test our window against a condition, if the condition is satisfactory then we will continue to expand our window.  If the condition is not, we will shrink our window and begin to try a different window, all while keeping track of the most favorable window we have seen.

First off, if we have no input array, then we have no subarray that we can return.

        if not nums or len(nums) == 0:
            return 0

 

If we do have an input array, we will initialize our left and right pointers to the beginning of it.  These will be used to measure our window later on.

        left, right = 0, 0

 

We will also create variables to track the running minimum window size, as well as a sum for each current window we will use later.

        min_size, current_sum = float('inf'), 0

 

Then, we will create a loop that will run while we still have numbers in the input array that we haven't considered in our window.

        while right < len(nums):

 

We can view it like this, our right pointer will be in charge of picking numbers and throwing them into the window.

Our left pointer will be in charge of sliding to the right while we have a window greater than or equal to the target so that we can try to shrink the window to make it valid again.

Let's throw a number into the window and add it to our current sum.  We will continue doing this until we have a sum that is greater than or equal to the target.

            current_sum += nums[right]

 

If the current sum is less than the target, we don't need to shrink our window so we will continue expanding.

Otherwise, we will need to start shrinking it until our current sum is less than the target.

            while current_sum >= target:

 

At that point, we will check if our window is the smallest window we have seen before.  This will be done by calculating the distance between the pointers, then seeing if that is smaller than the minimum size we have seen up to this point.

If it is, this window is the new smallest window.

                min_size = min(min_size, right-left+1)

 

Once we have checked the window size, we will drop the leftmost number from our sum and slide our pointer to the right past it so we can keep trying to get the smallest window possible.

                current_sum -= nums[left]
                left += 1

 

This is how we will be able to consider each window as we move along.

[2,3,1,2,4,3], target is 7.

[1,4,4], target is 4.

 

 

This is the overall picture of sliding window problems.  We will test against a condition, in this case, having the smallest sized subarray whose sum is greater than or equal to the target number.  If the condition is satisfactory, then we will continue to expand our window.  If the condition is not, we will decrease our window length to try a different window, all while keeping track of the most favorable window we have seen.

Once we have shrunk our window and now have a window whose sum is lesser than the target, we will expand it to try and get closer to the target again.

            right += 1

 

This will continue until our right pointer has gone past the end of the array, at which point we have considered the best windows.

If the minimum size still equals the infinity float then we never found an acceptable window, in which case we will return zero.

Otherwise, we will return the smallest window we were able to get.

        if min_size != float('inf'):
            return min_size
        else:
            return 0