862. Shortest Subarray with Sum at Least K

[mah-shamim]

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

[mah-shamim]

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: 862. Shortest Subarray with Sum at Least K

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function shortestSubarray($nums, $k) {
    $n = count($nums);
    
    // Initialize prefix_sum array.
    $prefix_sum = array_fill(0, $n + 1, 0);
    
    // Compute the prefix sum array.
    for ($i = 0; $i < $n; $i++) {
        $prefix_sum[$i + 1] = $prefix_sum[$i] + $nums[$i];
    }
    
    // Monotonic queue to store indices of the prefix_sum array.
    $deque = [];
    $minLength = PHP_INT_MAX;
    
    // Iterate over the prefix_sum array.
    for ($i = 0; $i < $n + 1; $i++) {
        // Remove elements from deque that do not form a valid subarray.
        while (count($deque) > 0 && $prefix_sum[$i] - $prefix_sum[$deque[0]] >= $k) {
            $minLength = min($minLength, $i - $deque[0]);
            array_shift($deque);  // Remove the front of the queue.
        }
        
        // Maintain the deque: remove all indices where prefix_sum[i] is less than the current value.
        while (count($deque) > 0 && $prefix_sum[$i] <= $prefix_sum[$deque[count($deque) - 1]]) {
            array_pop($deque);  // Remove the back of the queue.
        }
        
        // Add current index to the deque.
        array_push($deque, $i);
    }
    
    return $minLength == PHP_INT_MAX ? -1 : $minLength;
}

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

Explanation:

1. Prefix Sum Array:

   • We compute the cumulative sum of the array in the prefix_sum array. This helps in calculating the sum of any subarray nums[i...j] by using the formula prefix_sum[j+1] - prefix_sum[i].

2. Monotonic Queue:

   • The deque holds indices of the prefix_sum array in increasing order of values. We maintain this order so that we can efficiently find the smallest subarray whose sum is greater than or equal to k.

3. Sliding Window Logic:

   • As we traverse through the prefix_sum array, we try to find the smallest subarray using the difference between the current prefix_sum[i] and previous prefix_sum[deque[0]].
   • If the difference is greater than or equal to k, we calculate the subarray length and update the minimum length found.

4. Returning Result:

   • If no valid subarray is found, return -1. Otherwise, return the minimum subarray length.

Time Complexity:

• Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice (once when added to the deque and once when removed).
• Space Complexity: O(n) due to the prefix_sum array and the deque used to store indices.

This approach ensures that the solution runs efficiently even for large inputs.

[basharul-siddike]

Thanks to solve the "Shortest Subarray with Sum at Least K" problem efficiently

[mah-shamim]

Thanks