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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray with Sum at Least K

Number: 892

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Meta, Microsoft, Goldman Sachs

Problem Description

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

Key Insights

  • Use a prefix-sum array to quickly compute the sum of any subarray.
  • The difference between two prefix sums gives the sum of the subarray between their indices.
  • Maintain a monotonic deque that stores indices of the prefix-sum array in increasing order.
  • As you iterate through the prefix sums, check and update the answer when the difference meets or exceeds k.
  • Remove indices from the deque that are no longer potential candidates (either because they yield a subarray that is too long or their prefix sum is not optimal).

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in nums. Space Complexity: O(n) due to storing the prefix sum array and the deque.

Solution

We solve the problem by first constructing a prefix-sum array where each element p[i+1] equals p[i] plus nums[i]. For any two indices i and j (with i < j), the sum of the subarray nums[i] to nums[j-1] is p[j] - p[i]. We need this difference to be at least k. By using a deque, we can efficiently track and check for the shortest valid subarray.

The deque is maintained in increasing order of prefix sums:

  • As we iterate through the prefix sums, if the current prefix sum minus the smallest prefix sum from the deque is at least k, we update the minimum length.
  • We remove indices from the back if they offer no benefit (i.e., having a larger prefix sum when a smaller one has already been seen).
  • This ensures that we always consider the best candidate indices for forming a valid subarray.

Code Solutions

# Python solution for Shortest Subarray with Sum at Least K
from collections import deque

def shortestSubarray(nums, k):
    # Build the prefix sums, starting with an initial 0
    prefix_sums = [0]
    for num in nums:
        prefix_sums.append(prefix_sums[-1] + num)
    
    # Deque to store indices of prefix_sums in increasing order
    d = deque()
    res = float('inf')
    
    # Iterate over prefix sums
    for i, current_sum in enumerate(prefix_sums):
        # If the difference between current and oldest prefix sum is at least k,
        # update the result and remove the element from deque front.
        while d and current_sum - prefix_sums[d[0]] >= k:
            res = min(res, i - d[0])
            d.popleft()
        
        # Maintain increasing order of prefix sums in deque
        while d and prefix_sums[d[-1]] >= current_sum:
            d.pop()
        
        # Add current index
        d.append(i)
    
    return res if res != float('inf') else -1

# Example usage
if __name__ == "__main__":
    print(shortestSubarray([2, -1, 2], 3))  # Expected output: 3
← Back to All Questions