Minimum Size Subarray Sum

Intuition

• The mistake I made in this case was that I did right - left + 1 instead of right - left.
• It is very important for me to understand why this is the case.
• In the following situation:
  • 
  • If I do right - left + 1, I include index 5.
  • My confusion came from the fact that I was starting both left and right pointers at 0, so I assumed there would be a bug if I didn’t do right - left + 1.
  • However, in my code, I am specifically updating the right pointer after adding to my window. Then, my right pointer is pointing to an element that has not been added or past the end of the array.
  • Why it matters here is that I am checking for the minimum within my check where I only update the left pointer. Therefore, it leads to this situation.
  • To avoid this situation, I should have a while loop within my while loop that does a more tradiditional Sliding Window approach in which I update left to where it should be immediately.

Complexity

Runtime

$O(N)$ with Sliding Window approach.

Space

$O(1)$ for axillary variables

Code

Best Solution

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        cur_sum = 0
        res = inf
        left = 0
        for right in range(len(nums)):
            cur_sum += nums[right]
            
            while left <= right and cur_sum >= target:
                res = min(res, right - left + 1)
                cur_sum -= nums[left]
                left += 1
 
        return 0 if res == inf else res

Better Solution

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        cur_sum = 0
        minimum = inf
        for right in range(len(nums)):
            cur_sum += nums[right]
            while cur_sum >= target:
                minimum = min(minimum, right - left + 1)
                cur_sum -= nums[left]
                left += 1
 
        if minimum == inf:
            return 0
        return minimum

• This uses the more traditional sliding window approach with right - left + 1.
• Notice that it first adds to the sum, then immediately checks if that sum is >= target.
• Also notice that left may surpass right by 1, but then the cur_sum would be 0 in which case right would match up to equal left in the next iteration of the for loop.
• Also in this case, no while loop following the exit of the current for loop is necessary since right goes up by one every time, and any case wherein there is a minimum is processed immediately, rather than updating just one at a time like was the case with my previous code.

Cleaned Up

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = right = 0
        cur_sum = 0
        minimum = inf
 
        while right < len(nums):
            if cur_sum >= target:
                minimum = min(minimum, right - left)
                cur_sum -= nums[left]
                left += 1
            else:
                cur_sum += nums[right]
                right += 1
 
        while cur_sum >= target:
            minimum = min(minimum, right - left)
            cur_sum -= nums[left]
            left += 1
 
        if minimum == inf:
            return 0
        return minimum

Original

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = right = 0
        cur_sum = 0
        minimum = math.inf
 
        while right < len(nums):
            if cur_sum >= target:
                if right - left == 1:
                    return 1
                minimum = min(minimum, right - left)
                cur_sum -= nums[left]
                left += 1
            elif cur_sum < target:
                cur_sum += nums[right]
                right += 1
 
        while left < right and cur_sum >= target:
            minimum = min(minimum, right - left)
            cur_sum -= nums[left]
            left += 1
 
        if minimum == math.inf:
            return 0
        return minimum

• Unnecessary code wherein I checked if right - left < 1 on each iteration. This is not necessary since I always store the minimum window size, so even if my window size gets bigger, it cannot get any bigger than 1.
• Another note is that I do not need the left < right check since cur_sum will not be >= target if cur_sum == 0, though this is less intuitive.

Notes

---

References

• Minimum Size Subarray Sum