862. Shortest Subarray with Sum at Least K

862. Shortest Subarray with Sum at Least K

Difficulty: Hard

Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue

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:

We need to use a sliding window approach combined with prefix sums and a monotonic queue. Here's the step-by-step approach:

Steps:

1. 
   

   Prefix Sum:

   
   
   
   
   
   • First, calculate the prefix sum array, where each element at index i represents the sum of the elements from the start of the array to i. The prefix sum allows us to compute the sum of any subarray in constant time.
   
   
   
   


2. 
   

   Monotonic Queue:

   
   
   
   
   
   • We use a deque (double-ended queue) to maintain the indices of the prefix_sum array. The deque will be maintained in an increasing order of prefix sums.
   
   
   • This helps us efficiently find subarrays with the sum greater than or equal to k by comparing the current prefix sum with earlier prefix sums.
   
   
   
   


3. 
   

   Sliding Window Logic:

   
   
   
   
   
   • For each index i, check if the difference between the current prefix sum and any previous prefix sum (which is stored in the deque) is greater than or equal to k.
   
   
   • If so, compute the length of the subarray and update the minimum length if necessary.
   
   
   
   

Algorithm:

1. Initialize prefix_sum array with size n+1 (where n is the length of the input array). The first element is 0 because the sum of zero elements is 0.


2. Use a deque to store indices of prefix_sum values. The deque will help to find the shortest subarray that satisfies the condition in an efficient manner.


3. For each element in the array, update the prefix_sum, and check the deque to find the smallest subarray with sum greater than or equal to k.

Let's implement this solution in PHP: a star on GitHub or sharing the post on your favorite social networks 😍.