DDSA Solutions

862. Shortest Subarray with Sum at Least K

HardView on LeetCode
ArrayHash TableQueueSliding WindowMonotonic StackPrefix Sum
Time: O(n)
Space: O(n)

Problem Overview

Prefix sums + monotone deque.

Intuition

Prefix sums + monotone deque. For each index j, find the largest i < j where prefix[j]-prefix[i] >= k and j-i is minimized.

Algorithm

  1. 1Compute prefix sums.
  2. 2Use monotone increasing deque of indices.
  3. 3For each j: while deque front satisfies prefix[j]-prefix[front] >= k: update answer with j-front, pop front.
  4. 4While deque back has prefix[back] >= prefix[j]: pop back (useless). Push j.

Common Pitfalls

  • •Unlike sliding window, values can be negative so two-pointer doesn't work. The deque maintains increasing prefix sums.
862.cs
C#
// Approach: Prefix sums with a monotone deque; pop the front while the prefix difference meets the threshold, keep the back increasing.
// Time: O(n) Space: O(n)

public class Solution
{
    public int ShortestSubarray(int[] nums, int k)
    {
        int n = nums.Length;
        int ans = n + 1;
        var dq = new LinkedList<int>();
        var prefix = new List<long> { 0 };

        for (int i = 0; i < n; ++i)
            prefix.Add(prefix[prefix.Count - 1] + nums[i]);

        for (int i = 0; i < n + 1; ++i)
        {
            while (dq.Count > 0 && prefix[i] - prefix[dq.First.Value] >= k)
            {
                ans = Math.Min(ans, i - dq.First.Value);
                dq.RemoveFirst();
            }

            while (dq.Count > 0 && prefix[i] <= prefix[dq.Last.Value])
                dq.RemoveLast();

            dq.AddLast(i);
        }

        return ans <= n ? ans : -1;
    }
}
Was this solution helpful?

Related Problems