862. Shortest Subarray with Sum at Least K - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

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

Note:

The array can contain negative numbers.
The subarray must be contiguous.

Example Inputs and Outputs:

Example 1:
- Input: A = [2, -1, 2], K = 3
- Output: 3
- Explanation:
  The entire array has a sum of 2 + (-1) + 2 = 3 and is the shortest subarray with a sum at least 3.
Example 2:
- Input: A = [1, 2], K = 4
- Output: -1
- Explanation:
  No subarray has a sum of at least 4.
Example 3:
- Input: A = [1, 2, 3, 4, 5], K = 11
- Output: 3
- Explanation:
  The subarray [3, 4, 5] has a sum of 12 and is the shortest one with sum at least 11.

Constraints:

$(1 \leq A.length \leq 50{,}000)$
$(-10^5 \leq A[i] \leq 10^5)$
$(1 \leq K \leq 10^9)$

Hints for Solving the Problem:

Brute Force Idea:
- Can you try every possible subarray, compute its sum, and then find the minimum length subarray with sum (\geq K)?
- (This approach is too slow for large arrays due to its O(n²) time complexity.)
Prefix Sum and Deque:
- Compute a prefix sum array where prefix[i] is the sum of the first i elements (with prefix[0] = 0).
- For a subarray from index i to j, the sum is prefix[j] - prefix[i].
- Can you use a data structure (like a deque) to efficiently keep track of candidate indices such that you can quickly determine if a subarray ending at the current index has a sum (\geq K) while minimizing the length?
Monotonic Queue Insight:
- Maintaining a deque of indices with increasing prefix sums allows you to efficiently discard indices that are no longer useful.

Approach 1: Brute Force (Conceptual, O(n²))

Idea:

Iterate over all possible subarrays (using two nested loops) and calculate the sum.
Track the minimum length of a subarray that meets the condition (sum (\geq K)).
Drawback:

With up to 50,000 elements, this approach would be too slow.

Approach 2: Optimal Solution Using Prefix Sums and a Deque (O(n))

Step-by-Step Explanation:

Compute Prefix Sum:
- Let prefix[0] = 0.
- For each index (i) (from 1 to (n)), compute
  $[ \text{prefix}[i] = \text{prefix}[i-1] + A[i-1] ]$
- Now, the sum of subarray A[i...j-1] is prefix[j] - prefix[i].
Use a Deque to Track Candidate Indices:
- Maintain a deque (double-ended queue) that will store indices of the prefix array.
- The deque will hold indices in increasing order of their prefix values.
- For each index (j) (current index in the prefix array):
  - Check for Valid Subarrays:
    While the deque is not empty and
    $[ \text{prefix}[j] - \text{prefix}[\text{deque}[0]] \geq K ]$ update the answer as $(\min(\text{answer}, j - \text{deque}[0]))$ and remove the leftmost index.
  - Maintain Monotonicity:
    While the deque is not empty and
    $(\text{prefix}[j] \leq \text{prefix}[\text{deque}[\text{last}]])$ ,
    remove indices from the right end because the current index (j) offers a smaller prefix sum and is therefore a better candidate for future subarrays.
  - Append the current index (j) to the deque.
Result:
- If a valid subarray is found, return its length; otherwise, return -1.

Python Code (Optimal Deque Approach):

Python3

. . . .

Java Code (Optimal Deque Approach):

Java

. . . .

Complexity Analysis:

Time Complexity:
- Computing the prefix sum array takes O(n).
- The main loop processes each index at most twice (once when added and once when removed from the deque), resulting in an overall O(n) time complexity.
Space Complexity:
- The prefix sum array uses O(n) space.
- The deque uses O(n) in the worst case.
- Overall, the space complexity is O(n).

Edge Cases:

No Valid Subarray:
- If no subarray sums to at least K, the algorithm returns -1.
Single Element Array:
- When the array has a single element, the answer is 1 if that element is (\geq K); otherwise, -1.
Negative Numbers in Array:
- The presence of negative numbers means that the prefix sum array is not strictly increasing, which is why the deque is used to maintain candidate indices in increasing order.

Common Mistakes:

Not Using Prefix Sums:
- Trying to calculate subarray sums directly for every possible subarray results in O(n²) time complexity, which is inefficient.
Deque Maintenance Errors:
- Failing to maintain the monotonicity of the deque can lead to incorrect results.
- Not properly checking or updating the deque when a valid subarray is found.
Integer Overflow:
- When summing large numbers, use a larger data type (like long in Java) for prefix sums.

Alternative Variations:

Fixed-Length Subarrays:
- Variants where you must find subarrays of a fixed length that satisfy a sum condition.
Subarray with Maximum Sum:
- Problems such as the Maximum Subarray problem (Kadane’s algorithm) have a similar flavor but different goals.

Related Problems for Further Practice:

Maximum Subarray (LeetCode 53):
- Find the contiguous subarray with the largest sum.
Subarray Sum Equals K (LeetCode 560):
- Count the number of subarrays that sum to exactly K.
Minimum Size Subarray Sum (LeetCode 209):
- A similar sliding window problem for non-negative arrays.