Sliding window Minimum Size Subarray Sum

Question

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose 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.

I was able to successfully complete the question with the sliding window technique but I am looking for some help to optimize the time run /execute & generate the output. Current time complexity is O(n).

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        current_sum=nums[0]
        possible_combinations=[]
        result=float("inf")
        start=0
        end=0
        target_sum=target

        if sum(nums)<target:
            return 0
        elif target in nums:
            return 1
        else:
            while start < len(nums) and end < len(nums):
                if current_sum >= target_sum:
                    result=min(len(nums[start:end + 1]), result)
                    current_sum -= nums[start]
                    start += 1
                elif current_sum < target_sum:
                    end += 1
                    if end < len(nums):
                        current_sum += nums[end]
            if result ==float("inf"):
                return 0
        return result



        
        

Answer 1

There are 2 significant performance problems:

• You can remove the part:

    if sum(nums)<target:
        return 0
    elif target in nums:
        return 1
  

  This runs through your array twice on every run, even if it will probably only apply to a small percentage of test cases. Your while-loop covers those cases, taking a little more time though (so maybe test the effect, as if e.g. 95% of the test cases have sum(nums)<target, removing this edge case will slow your code down).

• In

   result=min(len(nums[start:end + 1]), result)
  

  you create a copy of the subarray just to get its length, while you know the length already: it is end-start+1. So you can replace it with

   result = min(end-start+1, result)
  

Additionally, you may want to try to end the loop early if the result is 1, as it cannot get lower than this - but it depends on the test data if that has a performance effect, or if this additional condition even increases the average run time:

while start < len(nums) and end < len(nums) and result != 1:

You can get rid of some of your comparisons, but those will probably only have a marginal performance impact (and probably don't make the code prettier or more readable). Some examples that come to mind:

• you do not need to test for elif current_sum < target_sum, since it is the only option left after if current_sum >= target_sum is false, so you can just use else

• you could add the test if you reached the end of your array into the else-block (as only there, end is increased), then you can remove it from the while loop (so you save one comparison when start is increased), e.g. something like:

   while start < len(nums) and result != 1:
       if current_sum >= target_sum:
           ...
       else:
           end += 1
           if end >= len(nums):
               break
           current_sum += nums[end]
  

• similarly for the start < len(nums) and result != 1-test that is only relevant if you are in the if-block

As a side note, your function currently would fail on an empty list (because current_sum=nums[0] would fail). It might be specified as not empty somewhere (although not by your docstring), apparently does not cause problems (until it does) and fixing it will most likely not improve performance, but it would fail any code audit, so you might want to keep it in mind.

Answer 2

You see this : len(nums[start:end + 1]) this is nothing but end - start + 1

In other words you are slicing the nums repeatedly which is not necessary.

You could write it as :

result = min(end - start + 1, result)