Introduction

The Shortest Subarray with Sum ≥ K problem involves finding the minimum length subarray whose sum is at least k.

Given:

  • an array
  • integer k

the task is to:

  • find shortest subarray
    whose sum is greater than or equal to k

If no such subarray exists:

  • return -1

This problem is one of the most important applications of:

Prefix Sum + Monotonic Deque

This problem helps in understanding:

  • prefix sums
  • monotonic queues
  • deque optimization
  • shortest range queries

Example

Input:arr = [2,-1,2]
k = 3

Output:
3

Explanation:
Entire array sum:
2 + (-1) + 2 = 3
Shortest valid subarray length:
3

Constraints

1 <= arr.length <= 10^5-10^5 <= arr[i] <= 10^5
  1 <= k <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all subarrays
  2. Compute subarray sums
  3. Track shortest valid length

This works but repeated sum calculations increase complexity.

Steps

  1. Traverse all start indices.
  2. Extend subarray.
  3. Compute running sum.
  4. Check if sum ≥ K.
  5. Update shortest length.

Dry Run

Input:[2,-1,2]k = 3
Subarrays:[2]Sum = 2Invalid
[2,-1]
Sum = 1
Invalid
[2,-1,2]
Sum = 3
Valid
Length = 3

Final Result:
3

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
All subarrays are generated.

Space Complexity: O(1)
Explanation:
Only variables are used.

Approach 2 : Prefix Sum + Monotonic Deque

Explanation

The optimized solution uses:

 Prefix Sum + Monotonic Increasing Deque

Idea:

  • build prefix sums
  • deque stores indices
    with increasing prefix sums

Why increasing?

  • smaller prefix sum helps
    form larger valid difference

Conditions:

  1. Remove useless larger prefix sums
  2. Remove valid shortest ranges
  3. Maintain increasing order

This gives:

  • O(n) solution

Steps

  1. Build prefix sum array.
  2. Create deque.
  3. Remove larger prefix sums.
  4. Check valid subarrays.
  5. Update shortest length.
  6. Return answer.

Dry Run

Input:[2,-1,2]
k = 3

Prefix Sum:
[0,2,1,3]

Process:
3 - 0 >= 3
Valid subarray found

Length:
3

Final Result:
3

Prefix Sum + Monotonic Deque Code

  1. Dry Run
Time Complexity: O(n)
Explanation:
Each index is inserted and removed from deque at most once.

Space Complexity: O(n)
Explanation:
Prefix sum array and dequestore up to n elements.

Edge Cases

  1. No valid subarray
  2. Single element valid
  3. Negative numbers present
  4. Large K value
  5. Entire array required

Why This Problem is Important

Shortest Subarray with Sum ≥ K helps in understanding:

  1. Prefix sums
  2. Monotonic deque
  3. Sliding range optimization
  4. Efficient subarray processing
  5. Advanced deque logic

It is one of the most important advanced deque interview problems.

Real-World Applications

Prefix sum and deque concepts are used in:

  1. Streaming analytics
  2. Financial monitoring
  3. Traffic analysis
  4. Resource allocation
  5. Real-time threshold systems

Common Mistakes

  1. Incorrect prefix sum usage
  2. Wrong deque ordering
  3. Forgetting larger prefix removal
  4. Missing no-answer case

Interview Tips

Interviewers often expect:

  1. Prefix sum explanation
  2. Monotonic deque reasoning
  3. O(n) optimization understanding

Always explain:

  • why increasing prefix sums matter
  • how shortest range is detected
  • why deque removes useless indices

Related Questions

  1. Sliding Window Maximum
  2. First Negative Integer in Window
  3. Constrained Subsequence Sum
  4. Daily Temperatures
  5. Maximum Sum Circular Subarray

Final Takeaway

The Shortest Subarray with Sum ≥ K problem is a fundamental advanced deque problem that teaches prefix sums and monotonic queue optimization techniques. Understanding this problem builds a strong foundation for advanced range-query and sliding-window interview problems.