0862-shortest-subarray-with-sum-at-least-k

Try it on leetcode

Description

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(Python)

from heapq import heappush, heappop
from collections import deque

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        #  nums = [2,-1,2], k = 3
        # 
        #  l = 0
        #  r = 0
        #  cur_Sum = 0
        #  shortest_length = float('inf')
        # r= 0  s
        #   cur_sum = 2  < 3
        # r = 0 -1
        #   cur_sum
        return self.deque(nums, k)

    def pq(self, nums: List[int], k: int) -> int:
        n = len(nums)
        shortest_subarray_length = float('inf')
        cumulative_sum = 0
        prefixSumHeap = []

        for i, num in enumerate(nums):
            cumulative_sum += num

            if cumulative_sum >= k:
                shortest_subarray_length = min(shortest_subarray_length, i + 1)
            while prefixSumHeap and cumulative_sum - prefixSumHeap[0][0] >= k:
                shortest_subarray_length = min(
                    shortest_subarray_length, i - heappop(prefixSumHeap)[1]
                )
        
            # Add current cumulative sum and index to heap
            heappush(prefixSumHeap, (cumulative_sum, i))

        # Return -1 if no valid subarray found
        return (
            -1
            if shortest_subarray_length == float("inf")
            else shortest_subarray_length
        )  

    def deque(self, nums: List[int], k: int) -> int:
        #  res = inf
        #  prefix sum array
        # maintain monotonicty in deque
        #    while cur - dq >= k
        #           i - dq
        #    pop back of deque if dq[-1] >= pre[i]
        # nums = [2,-1,2], k = 3
        res = float('inf')
        n = len(nums)
        prefix_sum = [0] * (n+1)  # [0 0 0 0]
        queue = deque()

        for i in range(1, n+1):
            prefix_sum[i] = prefix_sum[i-1] + nums[i -1] # 0 2 1 4
        
        for i in range(n + 1):
            while queue and prefix_sum[i] - prefix_sum[queue[0]] >= k :
                res = min(res, i - queue.popleft())
            
            while queue and prefix_sum[i] <= prefix_sum[queue[-1]]:
                queue.pop()
            queue.append(i) # 0 
        
        return res if res != float('inf') else -1

Dry Run