DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Shortest Subarray with Sum at Least K

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= 109

SOLUTION:

from collections import deque

# class Solution:
#     def shortestSubarray(self, nums: List[int], k: int) -> int:
#         n = len(nums)
#         currSum = 0
#         sumTill = [currSum]
#         currSmallest = (0, n + 1)
#         for num in nums:
#             currSum += num
#             sumTill.append(currSum)
#         for i in range(n + 1):
#             for j in range(i + 1, n + 1):
#                 if sumTill[j] - sumTill[i] >= k:
#                     if (j - i) < currSmallest[1] - currSmallest[0]:
#                         currSmallest = (i, j)
#                 if (j - i) >= currSmallest[1] - currSmallest[0]:
#                     break
#         diff = currSmallest[1] - currSmallest[0]
#         if diff == n + 1:
#             return -1
#         else:
#             return diff

# class Solution:
#     def shortestSubarray(self, nums: List[int], k: int) -> int:
#         n = len(nums)
#         currSum = 0
#         sumTill = [currSum]
#         for num in nums:
#             currSum += num
#             sumTill.append(currSum)
#         for j in range(1, n + 1):
#             for i in range(n + 1 - j):
#                 if sumTill[i + j] - sumTill[i] >= k:
#                     return j
#         return -1

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        currSum = 0
        sumTill = [currSum]
        for num in nums:
            currSum += num
            sumTill.append(currSum)
        minLen = n + 1
        q = deque()
        for i, s in enumerate(sumTill):
            while q and s <= sumTill[q[-1]]:
                q.pop()
            while q and s - sumTill[q[0]] >= k:
                minLen = min(minLen, i - q.popleft())
            q.append(i)
        if minLen == n + 1:
            return -1
        return minLen
Enter fullscreen mode Exit fullscreen mode

Top comments (0)