Shortest Subarray With Sum At Least K

Priority Queue Hard

Python Java C++

def shortestSubarray(nums: List[int], k: int) -> int:
    # Initialize result to maximum possible value
    shortestLen = float('inf')
    n = len(nums)
    
    # Initialize min-heap for prefix sums and cumulative sum
    prefixHeap = []
    currSum = 0
    
    # Process each element
    for i in range(n):
        # Update cumulative sum
        currSum += nums[i]
        
        # Check if current sum is sufficient
        if currSum >= k:
            shortestLen = min(shortestLen, i + 1)
        
        # Find valid subarrays using prefix sums
        while prefixHeap and currSum - prefixHeap[0][0] >= k:
            _, idx = heapq.heappop(prefixHeap)
            shortestLen = min(shortestLen, i - idx)
        
        # Add current sum to heap
        heapq.heappush(prefixHeap, (currSum, i))
    
    return shortestLen if shortestLen != float('inf') else -1

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        // Initialize result to the maximum possible integer value
        int shortestSubarrayLength = Integer.MAX_VALUE;
        long cumulativeSum = 0;
        // Min-heap to store cumulative sum and its corresponding index
        PriorityQueue> prefixSumHeap = new PriorityQueue<>(
            (a, b) -> Long.compare(a.getKey(), b.getKey())
        );
        
        // Iterate through the array
        for (int i = 0; i < n; i++) {
            // Update cumulative sum
            cumulativeSum += nums[i];
            // If cumulative sum is already >= k, update shortest length
            if (cumulativeSum >= k) {
                shortestSubarrayLength = Math.min(
                    shortestSubarrayLength,
                    i + 1
                );
            }
            
            // Remove subarrays from heap that can form a valid subarray
            while (
                !prefixSumHeap.isEmpty() &&
                cumulativeSum - prefixSumHeap.peek().getKey() >= k
            ) {
                // Update shortest subarray length
                shortestSubarrayLength = Math.min(
                    shortestSubarrayLength,
                    i - prefixSumHeap.poll().getValue()
                );
            }
            
            // Add current cumulative sum and index to heap
            prefixSumHeap.offer(new Pair<>(cumulativeSum, i));
        }
        
        // Return -1 if no valid subarray found
        return shortestSubarrayLength == Integer.MAX_VALUE
            ? -1
            : shortestSubarrayLength;
    }
}

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        int n = nums.size();
        // Initialize result to maximum possible value
        int shortestLen = INT_MAX;
        long long currSum = 0;
        
        // Min-heap to store {sum, index}
        priority_queue, 
                      vector>, 
                      greater<>> prefixHeap;
        
        // Process each element
        for (int i = 0; i < n; i++) {
            // Update cumulative sum
            currSum += nums[i];
            
            // Check if current sum is sufficient
            if (currSum >= k) {
                shortestLen = min(shortestLen, i + 1);
            }
            
            // Find valid subarrays using prefix sums
            while (!prefixHeap.empty() && 
                   currSum - prefixHeap.top().first >= k) {
                shortestLen = min(shortestLen, i - prefixHeap.top().second);
                prefixHeap.pop();
            }
            
            // Add current sum to heap
            prefixHeap.push({currSum, i});
        }
        
        return shortestLen == INT_MAX ? -1 : shortestLen;
    }
};

Previous Step Next Step Reset

Target Sum (k)

7

Current Sum

0

Shortest Length

∞

Priority Queue (Min Heap)

Click "Next Step" to begin the visualization

Problem Statement

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

Detailed Explanation

Approach

This solution uses a prefix sum approach combined with a priority queue to efficiently handle negative numbers and find the shortest valid subarray. Unlike simpler sliding window approaches, this method can handle negative numbers and efficiently skip invalid ranges.

Key Concepts

1. Prefix Sum Storage: Use priority queue to track prefix sums and their indices
2. Running Sum: Maintain cumulative sum using long to prevent overflow
3. Valid Subarray Detection: Check difference between current sum and previous prefix sums
4. Heap Property: Smallest prefix sum is always at top of heap

Algorithm Steps

1. Initialize tracking variables:
   • shortestLen to track minimum valid length
   • cumulativeSum for running sum
   • Priority queue for prefix sums and indices
2. For each element:
   • Update cumulative sum
   • Check if entire prefix forms valid subarray
   • Remove valid subarrays from queue and update minimum length
   • Add current prefix sum to queue

Time and Space Complexity

• Time Complexity: O(n log n)
  • Each element enters queue once: O(log n)
  • Each element leaves queue at most once: O(log n)
  • Total operations for n elements: O(n log n)
• Space Complexity: O(n)
  • Priority queue can store up to n elements
  • Each element stores sum and index

Why This Works

The solution handles complex cases through several key mechanisms:

• Negative Numbers:
  • Priority queue maintains ordered prefix sums
  • Can skip ranges containing negative sums
  • Handles decreasing cumulative sums efficiently
• Overflow Prevention:
  • Uses long/long long for sum calculations
  • Safely handles large positive and negative numbers
  • Prevents intermediate calculation errors
• Optimal Subarray Finding:
  • Always processes smallest possible prefix sum first
  • Guarantees shortest valid subarray is found
  • Efficiently removes unusable prefix sums

Edge Cases

• Empty array: Return -1
• All negative numbers: May require skipping elements
• Large positive numbers: Requires long for overflow prevention
• No valid subarray: Return -1
• Single element ≥ k: Return 1

Common Mistakes

• Using integer instead of long for sum calculations
• Not handling priority queue emptiness checks
• Incorrect comparison in priority queue ordering
• Not removing all valid prefix sums from queue
• Missing initialization of shortest length to MAX_VALUE