A monotonic stack that can also forget. Pop dominated candidates from the back, pop expired ones from the front, and the best candidate in the window is always at the front.
Two earlier patterns meet here. The sliding window moves a range across an array, but it cannot tell you the window’s maximum without rescanning. The monotonic stack throws away values that can never matter again, but it only ever grows from one end. Put the stack in a deque and you can also drop indices that slide out of the window. C# has no deque type, so this page shows what to use instead. Every index enters once and leaves once, so the whole pass is O(n).
best[i] = value + max(best[i-k..i-1]). Template B.n up to 105 with a window of size k. O(n × k) is too slow. O(n) is the target.Reading the figure. Cell colors match the fate of each index. Violet means stale: the index slid out of the window. Red means dominated: a newer, larger value arrived, so it can never be the max. Amber is the new value and green is the answer. Notice that the dominated values leave from the back, newest first.
Why indices, not values. The front check is “has this left the window?”, and only an index can answer that. Same rule as on the monotonic stack page.
Why O(n). Each index is appended once. It can be popped at most once, from one end or the other. So the total work across all the inner while loops is at most n pops, even though one step may pop many.
<= the new value.>= the new value.public static class SlidingWindowMin
{
/// <summary>Minimum of every window of size k, left to right.</summary>
/// <param name="nums">The values.</param>
/// <param name="k">Window size, from 1 up to nums.Length.</param>
/// <returns>One minimum per window, nums.Length - k + 1 values.</returns>
/// <example>
/// Mins([4, 2, 12, 3, 8, 1], 3) returns [2, 2, 3, 1].
/// </example>
public static List<int> Mins(int[] nums, int k)
{
// The deque is an int[] with two pointers. Live slots are head .. tail - 1.
// Each index is pushed once, so nums.Length slots never run out. No wraparound.
var window = new int[nums.Length]; // indices. nums[...] increases front to back.
int head = 0, tail = 0; // 0, 0: head == tail means empty
var output = new List<int>();
// index is the right edge of the window. The window is index - k + 1 .. index.
// Invariant at the top of each pass: window holds in-range, undominated indices.
for (int index = 0; index < nums.Length; index++)
{
int value = nums[index];
// Stale: index - k is the first position left of the window. Drop it.
while (head < tail && window[head] <= index - k)
head++; // pop front: move head right by one
// Dominated: an older value >= the new one can never be the minimum again.
// tail - 1: the back slot of the deque.
while (head < tail && nums[window[tail - 1]] >= value)
tail--; // pop back: move tail left by one
window[tail++] = index; // push back, then move tail one past it
// k - 1: the first index where a full window of k values exists.
if (index >= k - 1)
output.Add(nums[window[head]]); // the front holds the window minimum
}
return output;
}
}
Flip both comparisons for the maximum: pop the back while nums[window[tail - 1]] <= value. Everything else stays the same. Problem 1 is that flip.
Reading the figure. Each row is one pass of the loop. In the array, amber is the new value and blue is the rest of the window. Red text names values popped from the back as dominated. Violet text names a value dropped from the front as stale. The green deque cell is the front, which is the minimum written to out.
The Python version of this page uses collections.deque. .NET has no deque type. Queue<T> removes only from the front and Stack<T> only from the top. This pattern needs both ends. There are two good stand-ins.
int[] with head and tail. This page uses it everywhere.
head .. tail - 1. Pop front is head++. Pop back is tail--. Push back is window[tail++] = i.tail never passes n. An array of n slots is enough, and it never wraps around.LinkedList<int>. Shown below for Template A.
AddLast, RemoveFirst, RemoveLast, First and Last are all O(1).Why the array wins here. A monotonic deque only ever holds indices, and each index enters once. That is exactly the case where a plain array with two pointers is a complete deque. Use a real ring buffer, with % capacity on both pointers, only when items can be pushed again or the stream has no end. In an interview, say which one you picked and why in one sentence.
public static class SlidingWindowMinList
{
/// <summary>Same as SlidingWindowMin.Mins, with LinkedList as the deque.</summary>
/// <param name="nums">The values.</param>
/// <param name="k">Window size, from 1 up to nums.Length.</param>
/// <returns>One minimum per window, nums.Length - k + 1 values.</returns>
/// <example>
/// Mins([4, 2, 12, 3, 8, 1], 3) returns [2, 2, 3, 1].
/// </example>
public static List<int> Mins(int[] nums, int k)
{
// First is the front, Last is the back. Every end operation is O(1).
var window = new LinkedList<int>(); // indices. nums[...] increases front to back.
var output = new List<int>();
// index is the right edge. Invariant: window holds in-range, undominated indices.
for (int index = 0; index < nums.Length; index++)
{
// Stale: index - k is the first position left of the window.
while (window.Count > 0 && window.First!.Value <= index - k)
window.RemoveFirst();
// Dominated: an older value >= the new one can never be the minimum again.
while (window.Count > 0 && nums[window.Last!.Value] >= nums[index])
window.RemoveLast();
window.AddLast(index);
// k - 1: the first index where a full window of k values exists.
if (index >= k - 1)
output.Add(nums[window.First!.Value]);
}
return output;
}
}
Same logic, same answers. The tests run both versions on the same inputs. Pick the array for speed or the list for clarity. Both are O(n) overall.
public static class MinCostJumps
{
/// <summary>Cheapest walk from the first stone to the last, jumping 1 to k stones.
/// You pay costs[i] for every stone you land on, including the first.</summary>
/// <param name="costs">Cost of each stone, at least one stone.</param>
/// <param name="k">Longest jump allowed, at least 1.</param>
/// <returns>The minimum total cost to stand on the last stone.</returns>
/// <example>
/// Cheapest([1, 100, 1, 1, 100, 1], 2) returns 4.
/// </example>
public static int Cheapest(int[] costs, int k)
{
int n = costs.Length;
var best = new int[n]; // best[i]: cheapest total to stand on stone i
var window = new int[n]; // indices. best[...] increases front to back.
int head = 0, tail = 0; // live slots head .. tail - 1. Equal means empty.
// Invariant at the top of pass i: window holds indices i - k .. i - 1 that
// are not dominated, so best[window[head]] is the cheapest stone that can reach i.
for (int i = 0; i < n; i++)
{
// Stale: a stone before i - k is more than k stones back.
while (head < tail && window[head] < i - k)
head++;
// Recurrence: land on i from the cheapest reachable stone.
// Stone 0 has nothing before it, so it adds 0.
best[i] = costs[i] + (head < tail ? best[window[head]] : 0);
// Dominated: an older stone that costs at least as much is never better.
while (head < tail && best[window[tail - 1]] >= best[i]) // tail - 1: the back
tail--;
window[tail++] = i;
}
return best[^1]; // ^1: the last stone
}
}
The recurrence best[i] = cost[i] + min(best[i-k..i-1]) is O(n × k) if you scan. The deque turns the scan into reading window[head]. Any DP whose transition is “best of the last k states” gets this speed-up. Jump Game VI is this template with max in place of min.
Reading the figure. Each column is one stone. The front row is window[head], the cheapest stone in reach. Violet notes show a stone dropped from the front for being more than k back. Green stones form the cheapest walk, and the green cell is the answer, best[^1] = 4.
k ending at i, the first index is i - k + 1. So drop the front while it is <= i - k, or equally < i - k + 1.i >= k - 1.head < tail before window[head]. With LinkedList, First is null when empty.n, or n + 1 for prefix indices.< where <= is safe. Both give right answers for max and min. Popping on ties keeps the deque shorter. In Problem 4 with values stored instead of indices, ties must be kept. Indices avoid the question.Given an array nums and a window size k, return the maximum of each window of k consecutive values as the window slides from left to right.
public static class SlidingWindowMax
{
/// <summary>Maximum of every window of size k, left to right.</summary>
/// <param name="nums">The values.</param>
/// <param name="k">Window size, from 1 up to nums.Length.</param>
/// <returns>One maximum per window, nums.Length - k + 1 values.</returns>
/// <example>
/// MaxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) returns [3, 3, 5, 5, 6, 7].
/// </example>
public static int[] MaxSlidingWindow(int[] nums, int k)
{
// n - k + 1 windows: right edges k - 1 .. n - 1.
var result = new int[nums.Length - k + 1];
var window = new int[nums.Length]; // indices. nums[...] decreases front to back.
int head = 0, tail = 0; // live slots head .. tail - 1. Equal means empty.
// right is the right edge. The window covers right - k + 1 .. right.
// Invariant at the top of each pass: window holds in-range, undominated indices.
for (int right = 0; right < nums.Length; right++)
{
// Stale: right - k is one left of the window, so drop it and anything older.
while (head < tail && window[head] <= right - k)
head++;
// Dominated: an older value <= the new one can never be the max again.
while (head < tail && nums[window[tail - 1]] <= nums[right]) // tail - 1: back
tail--;
window[tail++] = right;
// k - 1: the first right edge with a full window of k values.
// right - k + 1 is the window's left edge, which is also its output slot.
if (right >= k - 1)
result[right - k + 1] = nums[window[head]]; // the front is the window max
}
return result;
}
}
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. The deque is shown as values.
1: deque [1]. Window not full.3: pops 1. Deque [3]. Not full.-1: deque [3, -1]. Emit 3.-3: deque [3, -1, -3]. Emit 3.5: 3 is stale, then 5 pops -3 and -1. Deque [5]. Emit 5.3: deque [5, 3]. Emit 5. Then 6 pops both, emit 6. Then 7 pops 6, emit 7.Reading the figure. Each row adds one value. Amber marks it in the array, blue marks the rest of its window. Red text lists values popped from the back because the new value is at least as big. At i=4 the 3 is popped from the front in violet, because index 1 left the window. The green cell is the front, the max of that window.
k = 1: every value is its own window, the output equals the input.k == nums.Length: one window, the output is [nums.Max()].k and the front check does all the work.<= keeps only the newest copy, which lives longest. Correct and shorter.Given an integer array nums, which may contain negatives, and an integer k, return the length of the shortest non-empty contiguous subarray whose sum is at least k. Return -1 if none exists.
nums[i:j] is prefix[j] - prefix[i]. For each j we want the largest i with prefix[i] <= prefix[j] - k.prefix[j] - prefix[front] >= k, record the length and drop the front. A later j would only give a longer subarray from that start.prefix[back] >= prefix[j], drop the back. Index j is later and no larger, so it beats back as a start for every future end.public static class ShortestSubarray
{
/// <summary>Length of the shortest subarray with sum at least k, or -1.</summary>
/// <param name="nums">Integers, may be negative.</param>
/// <param name="k">The target, at least 1.</param>
/// <returns>The shortest qualifying length, or -1 if none exists.</returns>
/// <example>
/// ShortestSubarrayAtLeastK([84, -37, 32, 40, 95], 167) returns 3.
/// </example>
public static int ShortestSubarrayAtLeastK(int[] nums, int k)
{
int n = nums.Length;
// prefix[j] is the sum of nums[0..j). n + 1 slots: prefix[0] = 0 is the empty prefix.
// long: n values near int.MaxValue would overflow an int sum.
var prefix = new long[n + 1];
for (int j = 0; j < n; j++)
prefix[j + 1] = prefix[j] + nums[j]; // + 1: prefix runs one ahead of nums
// n + 1 is longer than any real subarray, so it marks "none yet".
int best = n + 1;
// n + 1 slots: every prefix index is pushed once at most.
var starts = new int[n + 1]; // indices into prefix, prefix[...] increasing
int head = 0, tail = 0; // live slots head .. tail - 1. Equal means empty.
// end is a prefix index. nums[start..end) sums to prefix[end] - prefix[start].
// Invariant at the top of each pass: starts holds useful start indices below end.
for (int end = 0; end <= n; end++)
{
long total = prefix[end];
// Front: the oldest start works. No later end can give it a shorter answer.
while (head < tail && total - prefix[starts[head]] >= k)
best = Math.Min(best, end - starts[head++]); // read the front, then pop it
// Back: end is later and no larger, so it is a better start from now on.
while (head < tail && prefix[starts[tail - 1]] >= total) // tail - 1: the back
tail--;
starts[tail++] = end;
}
// Still the sentinel n + 1 means nothing qualified, so -1.
return best <= n ? best : -1;
}
}
nums = [2, -1, 2], k = 3, so prefix = [0, 2, 1, 3]:
end = 0, total 0: deque [0].end = 1, total 2: 2 - 0 < 3. Deque [0, 1].end = 2, total 1: 1 - 0 < 3. Back prefix 2 ≥ 1, pop index 1. Deque [0, 2].end = 3, total 3: 3 - 0 >= 3, length 3 - 0 = 3, pop index 0. 3 - 1 < 3, stop. Deque [2, 3].Reading the figure. On the left, each circle is prefix[index], plotted by height. The red circle is index 1. Index 2 comes later with a smaller prefix, so index 1 can never be the better start. The green dashed line joins the start and end of the answer. On the right, the deque holds start indices, front on the left.
>= k: length 1.-1.int is 32 bits and wraps on overflow. The prefix array is long[] so the sums stay exact.Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence such that any two consecutive chosen elements are at most k positions apart.
best[i] is the largest sum of a valid subsequence that ends at i.best[i] = nums[i] + max(0, best[j]) over i - k <= j < i. The 0 means “start fresh at i” when every earlier option is negative.k DP values, so Template B with max makes it O(1).best.Max(), since the best subsequence can end anywhere.public static class ConstrainedSubsetSum
{
/// <summary>Max sum of a non-empty subsequence with chosen indices at most k apart.</summary>
/// <param name="nums">Integers, at least one, may be negative.</param>
/// <param name="k">Largest allowed gap between consecutive chosen indices, at least 1.</param>
/// <returns>The maximum achievable sum.</returns>
/// <example>
/// MaxSum([10, 2, -10, 5, 20], 2) returns 37.
/// </example>
public static int MaxSum(int[] nums, int k)
{
// best[i]: largest sum of a valid subsequence ending at i. Clone gives a copy,
// so each slot starts as "take nums[i] alone".
var best = (int[])nums.Clone();
var window = new int[nums.Length]; // indices. best[...] decreases front to back.
int head = 0, tail = 0; // live slots head .. tail - 1. Equal means empty.
// Invariant at the top of pass i: window holds undominated indices in
// i - k .. i - 1, so best[window[head]] is the best predecessor for i.
for (int i = 0; i < nums.Length; i++)
{
// Stale: an index before i - k is too far back to precede i.
while (head < tail && window[head] < i - k)
head++;
if (head < tail)
{
// Math.Max(0, ...): a negative predecessor only hurts, so start fresh.
best[i] = nums[i] + Math.Max(0, best[window[head]]); // front is the max
}
// Dominated: an older index with a sum no larger is never the better pick.
while (head < tail && best[window[tail - 1]] <= best[i]) // tail - 1: the back
tail--;
window[tail++] = i;
}
return best.Max(); // the best subsequence may end anywhere
}
}
nums = [10, 2, -10, 5, 20], k = 2:
i = 0: best[0] = 10. Deque [0].i = 1: front 10, best[1] = 2 + 10 = 12. 12 pops index 0. Deque [1].i = 2: front 12, best[2] = -10 + 12 = 2. Deque [1, 2].i = 3: index 1 is still in range. best[3] = 5 + 12 = 17. Pops 2 and 1. Deque [3].i = 4: best[4] = 20 + 17 = 37. best.Max() is 37, from 10, 2, 5, 20.Reading the figure. Each column is one index. The front row shows which earlier state best[i] builds on. Green cells in the top row are the chosen subsequence. The grey -10 is skipped. Notice that i3 reads i1, two steps back, which is still inside k = 2.
Math.Max(0, ...) handles it.k >= nums.Length: any subsequence is allowed, so the answer is the sum of the positives, or the largest value if none are positive.best[^1] and there is no Math.Max(0, ...). Same deque.Given an integer array nums and an integer limit, return the length of the longest contiguous subarray in which the absolute difference between any two elements is at most limit.
max - min <= limit. So we need the window’s max and min at all times.highs has decreasing values, so its front is the max. lows has increasing values, so its front is the min.left moves past a front index, that front is stale and goes.public static class LongestSubarrayLimit
{
/// <summary>Longest subarray whose max minus min is at most limit.</summary>
/// <param name="nums">Integers, at least one.</param>
/// <param name="limit">Largest allowed difference, 0 or more.</param>
/// <returns>The length of the longest qualifying subarray.</returns>
/// <example>
/// LongestSubarray([10, 1, 2, 4, 7, 2], 5) returns 4.
/// </example>
public static int LongestSubarray(int[] nums, int limit)
{
int n = nums.Length;
// Two int[] deques, n slots each because every index is pushed once.
var highs = new int[n]; // indices. Values decrease, front is the max.
var lows = new int[n]; // indices. Values increase, front is the min.
int hHead = 0, hTail = 0; // highs live in hHead .. hTail - 1
int lHead = 0, lTail = 0; // lows live in lHead .. lTail - 1
int left = 0; // 0: the window starts at the first index
int best = 0; // 0: no window seen yet
// right is the new right edge. Invariant at the end of each pass: the window
// left .. right is valid, and both deques hold only indices in it.
for (int right = 0; right < n; right++)
{
int value = nums[right];
// Dominated in highs: older and no bigger, never the max again.
while (hHead < hTail && nums[highs[hTail - 1]] <= value) // - 1: the back
hTail--;
highs[hTail++] = right;
// Dominated in lows: older and no smaller, never the min again.
while (lHead < lTail && nums[lows[lTail - 1]] >= value) // - 1: the back
lTail--;
lows[lTail++] = right;
// Shrink while invalid. Each head is a front: the window max and min.
while ((long)nums[highs[hHead]] - nums[lows[lHead]] > limit) // long: no overflow
{
left++; // drop one index from the left edge
if (highs[hHead] < left) // the max fell out of the window
hHead++;
if (lows[lHead] < left) // the min fell out of the window
lHead++;
}
// + 1: right - left counts gaps. Add one to count the elements.
best = Math.Max(best, right - left + 1);
}
return best;
}
}
nums = [8, 2, 4, 7], limit = 4. Deques shown as values.
right = 0 (8): highs [8], lows [8]. Length 1.right = 1 (2): highs [8, 2], lows [2]. 8 - 2 > 4, so left = 1 and 8 leaves highs. Length 1.right = 2 (4): highs [4], lows [2, 4]. 4 - 2 <= 4. Length 2.right = 3 (7): highs [7], lows [2, 4, 7]. 7 - 2 > 4, so left = 2 and 2 leaves lows. 7 - 4 <= 4. Length 2.Reading the figure. Each row adds nums[right], shown in amber, and the blue cells are the rest of the window after any shrink. Deques read front to back, left to right. A violet cell is a front that went stale when left moved past it. Values popped from the back as dominated are not drawn. The green length is the best seen.
1. The deques are never empty inside the shrink loop, because right is in both and a single element always satisfies the limit.limit = 0: the longest run of equal values.SortedDictionary<int, int> of value counts, or two heaps with lazy deletion, also work at O(n log n). Name them, then explain why the deques are linear.max - min can overflow int. The code casts to long before it subtracts.int[] with head and tail is enough, because each index enters once. LinkedList<int> is the readable fallback.The deque here is a tool inside an algorithm. Pattern 23, Design: Hash Map plus Linked List, turns the same “cheap at both ends” idea into a data structure you build yourself, the shape behind the LRU cache.