A stack is the first data structure anyone learns and the last one people think to reach for. The trick in this part is not the stack itself. It is deciding what you refuse to keep in it.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Pattern 21 — The monotonic stack
For every element, find the next element to its right that is bigger.
Checking each one against everything after it is O(n²). The linear version comes from a single observation: while you are scanning left to right, some elements are still waiting for an answer. Keep exactly those, and nothing else.
When a new value arrives, it answers every waiting element smaller than itself — possibly several at once — and then joins the queue of waiters itself. Because each waiter is only ever resolved by the first value that beats it, the waiting list is always decreasing from bottom to top. That is what “monotonic” means here.
The stack holds indices still waiting for an answer, and their values always decrease from bottom to top. A new value taller than the top resolves it — and possibly several beneath it, all in the same step.
int[] a = [2, 1, 2, 4, 3];
int[] answer = new int[a.Length];
Array.Fill(answer, -1);
Stack<int> st = []; // indices, values DECREASING from bottom to top
for (int i = 0; i < a.Length; i++)
{
while (st.Count > 0 && a[st.Peek()] < a[i])
{
int j = st.Pop();
answer[j] = a[i];
Console.WriteLine($"i={i} a[i]={a[i]} resolves index {j} (value {a[j]}) -> next greater is {a[i]}");
}
st.Push(i);
Console.WriteLine($"i={i} a[i]={a[i]} push stack(values)=[{string.Join(",", st.Select(k => a[k]).Reverse())}]");
}
Console.WriteLine($"\nleft unresolved: [{string.Join(", ", st.Select(k => $"a[{k}]={a[k]}").Reverse())}] -> no greater element exists");
Console.WriteLine($"a = [{string.Join(", ", a)}]");
Console.WriteLine($"answer = [{string.Join(", ", answer)}]");It prints:
i=0 a[i]=2 push stack(values)=[2]
i=1 a[i]=1 push stack(values)=[2,1]
i=2 a[i]=2 resolves index 1 (value 1) -> next greater is 2
i=2 a[i]=2 push stack(values)=[2,2]
i=3 a[i]=4 resolves index 2 (value 2) -> next greater is 4
i=3 a[i]=4 resolves index 0 (value 2) -> next greater is 4
i=3 a[i]=4 push stack(values)=[4]
i=4 a[i]=3 push stack(values)=[4,3]
left unresolved: [a[3]=4, a[4]=3] -> no greater element exists
a = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]Watch i=3. The value 4 resolves two waiting elements in one step, and neither is revisited. The two left on the stack at the end never got an answer, which is exactly right — nothing bigger exists to their right.
The nested while looks quadratic. It is not: every index is pushed exactly once and popped at most once, so the total work across the whole scan is at most 2n.
Cost: O(n) time, O(n) space.
Reach for it when the question is next greater, previous smaller, how far until something taller, stock span, daily temperatures. Flip the comparison to get the smaller variants.
Pattern 22 — The largest rectangle in a histogram
This is the pattern above, earning its keep.
A rectangle using bar i at full height extends right until it meets a shorter bar, and left until it meets a shorter bar. So its width is bounded by the next smaller element on each side — which is pattern 21, run twice.
The monotonic stack gives both boundaries in one pass. When a bar is popped, the value arriving is its right boundary, and whatever is now beneath it on the stack is its left boundary.
Every rectangle is limited by the first shorter bar on each side — which is the next-smaller-element question, twice. That is why the monotonic stack solves it: popping a bar tells you both boundaries at once.
int[] h = [2, 1, 5, 6, 2, 3];
// The sentinel: a zero-height bar past the end forces every remaining bar to
// be resolved, so there is no separate drain loop after the scan.
int[] bars = [.. h, 0];
Stack<int> st = [];
int best = 0;
for (int i = 0; i < bars.Length; i++)
{
while (st.Count > 0 && bars[st.Peek()] >= bars[i])
{
int top = st.Pop();
int height = bars[top];
int left = st.Count == 0 ? -1 : st.Peek();
int width = i - left - 1;
int area = height * width;
Console.WriteLine($"i={i} pop bar {top} (height {height}) spans ({left}..{i}) exclusive width {width} area {area}");
best = Math.Max(best, area);
}
st.Push(i);
}
Console.WriteLine($"\nlargest rectangle: {best}");It prints:
i=1 pop bar 0 (height 2) spans (-1..1) exclusive width 1 area 2
i=4 pop bar 3 (height 6) spans (2..4) exclusive width 1 area 6
i=4 pop bar 2 (height 5) spans (1..4) exclusive width 2 area 10
i=6 pop bar 5 (height 3) spans (4..6) exclusive width 1 area 3
i=6 pop bar 4 (height 2) spans (1..6) exclusive width 4 area 8
i=6 pop bar 1 (height 1) spans (-1..6) exclusive width 6 area 6
largest rectangle: 10Two details are load-bearing.
The sentinel. A zero-height bar is appended past the end of the array. Without it, any bars still on the stack when the scan finishes need a separate drain loop with slightly different logic — and that duplicated logic is where the bug goes. A bar of height zero is shorter than everything, so it forces every remaining bar to be resolved by the main loop.
The width. It is i - left - 1, where left is the index below the popped bar on the stack, not the popped bar itself. Both boundaries are exclusive: the span runs strictly between two shorter bars. Getting this off by one gives an answer that looks plausible on small inputs.
Cost: O(n) time, O(n) space.
Reach for it when you need the biggest rectangle, the largest square in a binary matrix (run this once per row), or any “how wide can this extend before something blocks it” question.
Pattern 23 — Matching brackets
The plain use of a stack, and worth including because the details are where it goes wrong.
static bool Valid(string s)
{
Dictionary<char, char> pairs = new() { [')'] = '(', [']'] = '[', ['}'] = '{' };
Stack<char> st = [];
foreach (char c in s)
{
if (pairs.ContainsValue(c)) { st.Push(c); continue; }
if (!pairs.TryGetValue(c, out char open)) continue; // not a bracket
if (st.Count == 0 || st.Pop() != open) return false;
}
return st.Count == 0;
}
foreach (string s in new[] { "{[()]}", "([)]", "(((", "", "a(b[c]d)e" })
Console.WriteLine($"{$"\"{s}\"",12} -> {Valid(s)}");It prints:
"{[()]}" -> True
"([)]" -> False
"(((" -> False
"" -> True
"a(b[c]d)e" -> TrueThe two cases people forget are both in that output. "(((" fails not because a mismatch was found but because the stack is not empty at the end — every opener needs a partner. And "" is valid, which falls out of the same check rather than needing a special case.
"([)]" is the reason a stack is required at all. A counter for each bracket type would call it valid: one (, one ), one [, one ]. Nesting is about order, and only a stack records order.
Cost: O(n) time, O(n) space.
Reach for it when anything nests — brackets, tags, expression parsing, undo history.
Pattern 24 — A stack that knows its own minimum
Report the minimum of everything on the stack, in O(1), while pushes and pops keep happening.
Keeping a single min variable fails on pop: when the minimum is removed, the next-smallest has to be found again, and that is O(n).
The fix is to stop treating the minimum as one fact about the whole stack. Store, with each element, the minimum of everything at or below it.
One extra int per element buys O(1) Min(). The reason it survives popping is that each entry’s minimum was computed from what was below it, never from what came after.
// Each entry carries the minimum of everything at or below it. That makes Min
// a peek, and costs one extra int per element.
Stack<(int value, int min)> st = [];
void Push(int v)
{
int min = st.Count == 0 ? v : Math.Min(v, st.Peek().min);
st.Push((v, min));
Console.WriteLine($"push {v,3} min is now {min,3} stack=[{string.Join(" ", st.Select(x => $"{x.value}/{x.min}").Reverse())}]");
}
foreach (int v in new[] { 5, 2, 7, 2, 9 }) Push(v);
Console.WriteLine();
while (st.Count > 0)
{
var (v, m) = st.Peek();
Console.WriteLine($"top {v,3} Min() = {m,3}");
st.Pop();
}It prints:
push 5 min is now 5 stack=[5/5]
push 2 min is now 2 stack=[5/5 2/2]
push 7 min is now 2 stack=[5/5 2/2 7/2]
push 2 min is now 2 stack=[5/5 2/2 7/2 2/2]
push 9 min is now 2 stack=[5/5 2/2 7/2 2/2 9/2]
top 9 Min() = 2
top 2 Min() = 2
top 7 Min() = 2
top 2 Min() = 2
top 5 Min() = 5Popping needs no recomputation at all, and the reason is worth stating plainly: each entry’s minimum was computed from what was below it, never from what came after. Removing later entries cannot invalidate it.
Cost is one extra int per element. Look at the pop sequence in the output — 5 correctly reports its own minimum as 5 once everything above it is gone.
Cost: O(1) for push, pop and min. O(n) space.
Reach for it when you need a running aggregate that survives popping. The same shape works for max, or for gcd.
Pattern 25 — The container C# does not ship
Stack<T> and Queue<T> are both here and both fine. There is no array-backed deque — no ArrayDeque.
LinkedList<T> does the job, and it is what part 2’s sliding-window maximum used. It also allocates a node object for every element, and at contest input sizes that allocation shows up. A ring buffer over a single array does not, and it is short enough to type from memory.
C# ships Stack<T> and Queue<T> but no array-backed deque. LinkedList<T> fills the gap and allocates one node object per element; a ring buffer allocates one array, and is about twenty lines.
var d = new Deque(8);
d.PushBack(1); d.PushBack(2); d.PushBack(3);
Console.WriteLine($"pushed 1,2,3 at the back {d}");
d.PushFront(0);
Console.WriteLine($"pushed 0 at the front {d} (head wrapped round to the end of the array)");
Console.WriteLine($"first={d.First} last={d.Last}");
Console.WriteLine($"popFront -> {d.PopFront()} {d}");
Console.WriteLine($"popBack -> {d.PopBack()} {d}");
Console.WriteLine();
Stack<int> st = []; st.Push(1); st.Push(2);
Queue<int> q = []; q.Enqueue(1); q.Enqueue(2);
Console.WriteLine($"Stack<int> Peek={st.Peek()} LIFO — Push / Pop / Peek");
Console.WriteLine($"Queue<int> Peek={q.Peek()} FIFO — Enqueue / Dequeue / Peek");
Console.WriteLine($"Deque {d} both ends, one array, no per-item allocation");
// In a file-based app, type declarations come AFTER the top-level statements.
class Deque(int cap)
{
readonly int[] buf = new int[cap];
int head = 0, count = 0;
public int Count => count;
public int First => buf[head];
public int Last => buf[(head + count - 1) % buf.Length];
public void PushBack(int v) { buf[(head + count) % buf.Length] = v; count++; }
public void PushFront(int v) { head = (head - 1 + buf.Length) % buf.Length; buf[head] = v; count++; }
public int PopFront() { int v = buf[head]; head = (head + 1) % buf.Length; count--; return v; }
public int PopBack() { count--; return buf[(head + count) % buf.Length]; }
public override string ToString()
{
var parts = new List<int>();
for (int i = 0; i < count; i++) parts.Add(buf[(head + i) % buf.Length]);
return "[" + string.Join(", ", parts) + "]";
}
}It prints:
pushed 1,2,3 at the back [1, 2, 3]
pushed 0 at the front [0, 1, 2, 3] (head wrapped round to the end of the array)
first=0 last=3
popFront -> 0 [1, 2, 3]
popBack -> 3 [1, 2]
Stack<int> Peek=2 LIFO — Push / Pop / Peek
Queue<int> Peek=1 FIFO — Enqueue / Dequeue / Peek
Deque [1, 2] both ends, one array, no per-item allocationThe whole idea is % buf.Length. Pushing at the front moves head backwards and wraps it to the end of the array; nothing is shifted, and the elements are no longer stored in their logical order. ToString walks head, head+1, … modulo the length to recover it.
Note the + buf.Length in PushFront. In C#, -1 % 8 is -1, not 7 — the % operator keeps the sign of the left operand. Omitting that term gives a negative index, and the exception it throws is nowhere near the line that caused it.
Cost: O(1) at both ends, one array allocated once.
Reach for it when you need both ends — sliding window maximum, 0-1 BFS in part 8, or any BFS where some edges cost nothing.
What to remember
-
A monotonic stack holds only the elements still waiting for an answer. They come out ordered because each is resolved by the first value that beats it.
-
The nested
whileis still linear. Each index enters once and leaves once. Say that to yourself rather than trusting the shape of the code. -
Use a sentinel instead of a drain loop. A zero-height bar past the end forces the main loop to resolve everything, and removes the duplicated logic where bugs live.
-
Histogram widths are exclusive on both sides.
i - left - 1, withlefttaken from the stack after the pop. -
An unclosed bracket is a non-empty stack at the end. That check is what makes
"((("fail and""pass, with no special cases. -
A min-stack stores the minimum with each element, not once. It survives popping because it only ever looked downwards.
-
C# has no array deque, and
-1 % 8is-1. Add the length before taking the modulus, every time.
Part 6 is the containers proper: dictionaries, custom comparers, coordinate compression, and PriorityQueue<TElement, TPriority> — which only arrived in .NET 6, and which a lot of older C# contest material still works around.