Problem Statement in English

You’re given an array nums, and an integer k.

Your task is to return the length of the shortest subarray that has a sum >= k.

Approach

Brute forcing this is definitely an option, but we can do better. Hence we won’t go into the nested loop approach.

We’ll cover the linear time approach that uses the Sliding Window technique with a dynamic window size. The mechanics of this approach have been discussed in this problem.

Solution in Python


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # init `ans` to a really large value
        ans = float("inf")

        # sum of elements in the current window
        currentSum = 0

        # left pointer
        left = 0

        # managed right pointer
        for r in range(len(nums)):
            # update the current sum
            # as right pointer moves ahead
            currentSum += nums[right]

            # if `currentSum` > target then the current window
            # satisfies the requirements and we should move the left pointer forward
            # this means we need to update the current sum 
            # as well as the length of the shortest subarray,
            # that satisfies the given conditions
            while currentSum >= target:
                ans = min(ans, right - left + 1)

                currentSum -= nums[left]
                left += 1

        # type cast to int so that type checking doesn't complain
        return int(ans) if ans != float("inf") else 0

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only use a couple integer variables.

And we are done.