We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray with Sum at Least K

Difficulty: Hard

Problem 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.

Key Insights

  • A subarray is a contiguous part of an array.
  • We can use prefix sums to keep track of the sums of subarrays.
  • A monotonic queue can help efficiently find the shortest subarray that meets the sum requirement.
  • The problem can be approached using a sliding window technique combined with binary search.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will utilize a prefix sum array to store cumulative sums of the input array. We will then use a monotonic queue to maintain the indices of the prefix sums in a way that allows us to efficiently find the shortest subarray with a sum of at least k. The algorithm involves iterating through the prefix sums and checking the conditions using the queue to find valid subarrays.

Code Solutions

def shortestSubarray(nums, k):
    from collections import deque

    n = len(nums)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]

    min_length = float('inf')
    dq = deque()

    for i in range(n + 1):
        while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
            min_length = min(min_length, i - dq.popleft())
        while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
            dq.pop()
        dq.append(i)

    return min_length if min_length != float('inf') else -1
← Back to All Questions