A stack that refuses to hold anything out of order. Whatever it evicts, it evicts at the exact moment that item’s answer becomes known.
Every problem here has the same brute force. For each element, scan outward until you find the next bigger or smaller one. That is O(n²). A stack kept in sorted order makes it O(n). Each element is pushed once and popped once. The hard part is not the code. It is seeing that the question is a “next greater” question in disguise.
In C# the tool is Stack<int> with Push, Pop, Peek and Count. All four are O(1). The Python version of this page is here.
LinkedList<int> or an int[] ring buffer.while loop looks quadratic and is not. Every index enters the stack once and leaves once.Reading the figure. Blue bars sit on the stack, tallest at the bottom. The amber 76 arrives. The red arrows show it popping 69, 71 and 75 in that order. Each pop writes 76 as that bar’s answer.
n pops in the whole run. The inner while may run many times on one pass and zero times on the next. But the total inner steps over the whole loop is at most n. Total: O(n). This is the same accounting as the sliding window.All four are the same loop. Only the comparison and the reading point change. Write this list out before coding and you will not get the sign backwards.
stack top < current.stack top > current.stack top < current.stack top > current.public static class NextGreater
{
/// <summary>For each index, the index of the next strictly greater value.</summary>
/// <param name="nums">The values to scan.</param>
/// <returns>answer[i] is the index of the next greater value, or -1 if none.</returns>
/// <example><c>NextGreater.Indices([2, 1, 3])</c> returns <c>[2, 2, -1]</c>.</example>
public static int[] Indices(int[] nums)
{
// -1 means "no greater value to the right". Every slot starts there.
var answer = new int[nums.Length];
Array.Fill(answer, -1);
// Indices, not values. nums at those indices is non-increasing.
var stack = new Stack<int>();
// index is the current position. 0: start at the first element.
// Invariant: the stack holds every earlier index still waiting for an answer.
for (int index = 0; index < nums.Length; index++)
{
// Everything smaller than nums[index] has just found its answer.
// Count > 0 first: Peek on an empty stack throws.
while (stack.Count > 0 && nums[stack.Peek()] < nums[index])
answer[stack.Pop()] = index;
stack.Push(index); // index now waits for its own greater value
}
return answer; // anything left on the stack keeps -1
}
}Store indices, not values. You can always read the value from the index. You cannot get a distance back from a value.
public static class SentinelFlush
{
/// <summary>Runs an increasing stack with a fake 0 bar at the end.</summary>
/// <param name="heights">Non-negative bar heights.</param>
/// <param name="resolve">Per-problem work for a popped bar, called as
/// resolve(popped, index). index is the first bar to its right that is not taller.
/// Example: Largest Rectangle computes the popped bar's area here.</param>
/// <example><c>SentinelFlush.Run([2, 4, 3], log)</c> calls log(1, 2), log(2, 3),
/// then log(0, 3).</example>
public static void Run(int[] heights, Action<int, int> resolve)
{
var stack = new Stack<int>();
int n = heights.Length;
// index runs 0..n. The extra index n is a fake bar of height 0.
// 0 is lower than any real bar, so it pops everything still stacked.
for (int index = 0; index <= n; index++)
{
int height = index == n ? 0 : heights[index];
// >= pops equal bars too. Count > 0 guards Peek.
while (stack.Count > 0 && heights[stack.Peek()] >= height)
resolve(stack.Pop(), index);
stack.Push(index);
}
}
}A sentinel removes the “now drain whatever is left” block after the loop. You get one code path instead of two. The leftover case is where bugs live. C# arrays cannot grow, so the sentinel is the index == n check, not an appended element.
Reading the figure. Blue bars are still on the stack. Green bars have been popped and resolved. On the left the 3 pops the 4. But bars 2 and 3 are stranded when the input runs out. On the right the amber sentinel 0 arrives last. The red arrows show it popping both stranded bars. No cleanup code is needed.
while.new int[n] fills with 0. You need Array.Fill(answer, -1) when the default is -1.< versus <= with equal values. Strict keeps equal elements stacked. Non-strict pops them. For Largest Rectangle either works. For “next strictly greater” only strict is right. Ask what equality should mean.Peek on an empty stack. It throws InvalidOperationException. Always test stack.Count > 0 && … first. The && short-circuits, so Peek never runs on an empty stack. TryPeek(out var top) also works.List<int> and RemoveAt(0). That shifts every element, so it is O(n). A stack removes from the end. Use Stack<int>, or a List<int> with RemoveAt(list.Count - 1).int[] of size n plus a top counter. Push is stack[top++] = i. Pop is stack[--top]. It avoids the bounds and version checks in Stack<int>. In an interview, Stack<int> reads better. Mention the array form only if asked about speed.Given daily temperatures, return an array where answer[i] is the number of days you must wait after day i for a warmer temperature. If no warmer day comes, put 0.
new int[n] is already all 0, so no cleanup is needed.public static class DailyTemperatures
{
/// <summary>Days to wait for a warmer temperature, per day.</summary>
/// <param name="temperatures">Daily temperature readings.</param>
/// <returns>answer[i] is the number of days after i until a warmer day, or 0.</returns>
/// <example><c>DailyTemperatures.Wait([73, 74, 75, 71, 69, 72, 76, 73])</c>
/// returns <c>[1, 1, 4, 2, 1, 1, 0, 0]</c>.</example>
public static int[] Wait(int[] temperatures)
{
// C# fills new arrays with 0, which means "no warmer day ahead".
var answer = new int[temperatures.Length];
var stack = new Stack<int>(); // indices of days still waiting. Temps decrease
// index is today. 0: start at the first day.
// Invariant: the stack holds every earlier day with no warmer day yet,
// coldest on top.
for (int index = 0; index < temperatures.Length; index++)
{
// Today is warmer than everything waiting on top of the stack,
// so it is the answer for all of them. Count > 0 guards Peek.
while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[index])
{
int earlier = stack.Pop();
answer[earlier] = index - earlier; // days waited: the gap in index
}
stack.Push(index); // today now waits for its own warmer day
}
// Whatever is still stacked never warmed up, and 0 is already there.
return answer;
}
}[73, 74, 75, 71, 69, 72, 76, 73], one line per day:
[0].[1].[2].[2, 3].[2, 3, 4].[2, 5].[6].[6, 7].Indices 6 and 7 stay stacked and keep their 0. The stack is shown bottom to top.
Reading the figure. Each bar is one day. A red arrow runs from a day to the warmer day that popped it off the stack. The cell under each bar is the wait, which is the gap between the two day numbers. Green days found an answer. Blue days 6 and 7 never get popped, so they keep 0.
The worst case for space is a strictly decreasing input. Nothing is ever popped, so the stack holds all n indices. Name it when asked.
1 except the last.< is strict, so nothing pops and all answers are 0. Equal is not warmer. Confirm that reading.Given a circular array, return the next greater element for each position. The search wraps past the end and back to the start. Use -1 where none exists.
2n times and index with i % n. Two laps are always enough. After one full lap, every element has seen every other one. Then add one rule: only push indices during the first lap. The second lap exists only to resolve leftovers, so it must not create new ones.if (i < n) guard on the push is the whole difference from the plain version.public static class NextGreaterCircular
{
/// <summary>Next greater element for each position in a circular array.</summary>
/// <param name="nums">The circular array. The search wraps past the end.</param>
/// <returns>answer[i] is the first value greater than nums[i], scanning forward
/// and wrapping around, or -1 if there is none.</returns>
/// <example><c>NextGreaterCircular.Solve([1, 2, 1])</c> returns <c>[2, -1, 2]</c>.
/// </example>
public static int[] Solve(int[] nums)
{
int n = nums.Length;
var answer = new int[n];
Array.Fill(answer, -1); // -1: "no greater value", the default
var stack = new Stack<int>(); // indices. nums at those is non-increasing
// Two laps. The first seeds the stack, the second resolves the wrap-around.
// i runs 0..2n-1: 2 * n covers both laps. 0: start of lap one.
for (int i = 0; i < 2 * n; i++)
{
int value = nums[i % n]; // % n: wrap i back into 0..n-1
// Count > 0 guards Peek. The top is the latest index still waiting.
while (stack.Count > 0 && nums[stack.Peek()] < value)
answer[stack.Pop()] = value;
if (i < n) // i < n: first lap only. Never push on lap two
stack.Push(i);
}
return answer;
}
}nums = [1, 2, 1], so the loop runs 6 times:
[-1, -1, -1].[2, -1, -1].[2, -1, -1].[2, -1, -1].[2, -1, 2].[2, -1, 2].Index 1 holds the array maximum, so it keeps -1. That is correct.
Reading the figure. The six cells are the loop running 2n times over [1, 2, 1]. Blue cells are lap 1, where indices are pushed. Dashed cells are lap 2, where nothing is pushed. Each green arc is a pop that writes an answer. Index 2 only finds its answer because lap 2 wraps back to the 2 at the front.
2n passes is still O(n). Do not let the doubling talk you into calling it quadratic.
public static class NextGreaterElementI
{
/// <summary>Next Greater Element I. nums1 is a subset of nums2. Solve on nums2,
/// then look each nums1 value up.</summary>
/// <param name="nums1">The values to answer for. All appear in nums2.</param>
/// <param name="nums2">Distinct values to scan.</param>
/// <returns>For each nums1 value, its next greater value in nums2, or -1.</returns>
/// <example><c>NextGreaterElementI.Solve([4, 1, 2], [1, 3, 4, 2])</c> returns
/// <c>[-1, 3, -1]</c>.</example>
public static int[] Solve(int[] nums1, int[] nums2)
{
var greater = new Dictionary<int, int>(); // value -> next greater value in nums2
var stack = new Stack<int>(); // values this time, since nums2 has no duplicates
// Invariant: the stack holds earlier values with no greater value yet.
foreach (int value in nums2)
{
// value is the answer for every smaller value on top of the stack.
while (stack.Count > 0 && stack.Peek() < value)
greater[stack.Pop()] = value;
stack.Push(value);
}
// -1: values never popped have no greater value to the right.
return [.. nums1.Select(value => greater.GetValueOrDefault(value, -1))];
}
}Here the values are distinct, so a value-keyed Dictionary is safe. The stack can hold values directly. When duplicates are possible, go back to indices. GetValueOrDefault replaces Python’s dict.get(key, default).
[5, 5, 5]: all -1, because < is strict.-1. There may be several copies of it.[-1].Given an elevation map where height[i] is the height of a bar of width 1, compute how much rain water is trapped after it rains.
i is Math.Min(tallest bar to the left, tallest bar to the right) - height[i], or zero if that is negative. The shorter of the two walls holds the water in. That is why the min is there. Every solution below is a different way to get those two maxima cheaply.public static class RainWaterStack
{
/// <summary>Total rain water trapped above an elevation map. Fills the terrain
/// in horizontal layers. Each pop finds a basin floor. The bar under it on the
/// stack is the left wall, and the arriving bar is the right wall.</summary>
/// <param name="height">Non-negative bar heights.</param>
/// <returns>Total trapped water.</returns>
/// <example><c>RainWaterStack.Trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])</c>
/// returns <c>6</c>.</example>
public static int Trap(int[] height)
{
int total = 0; // 0: no water counted yet
var stack = new Stack<int>(); // indices. Heights non-increasing
// right is the arriving bar. 0: start at the first bar.
// Invariant: the stack holds bars that may still be a left wall,
// tallest at the bottom.
for (int right = 0; right < height.Length; right++)
{
int bar = height[right];
// A taller bar closes off one or more basins to its left.
// The top of the stack is the lowest waiting bar.
while (stack.Count > 0 && height[stack.Peek()] < bar)
{
int floor = stack.Pop();
if (stack.Count == 0)
break; // 0 left: no left wall, so the water spills out
int left = stack.Peek(); // the new top is the left wall
// - 1: count only the cells strictly between the two walls.
int width = right - left - 1;
// Water rises to the lower wall, above the floor already filled.
int depth = Math.Min(height[left], bar) - height[floor];
total += width * depth;
}
stack.Push(right);
}
return total;
}
}public static class RainWaterTwoPointers
{
/// <summary>Same answer in O(1) space, closing in from both ends. If the tallest
/// bar seen from the left is no taller than the tallest seen from the right, the
/// left max is the binding wall for the left position. So that side is safe to
/// settle now.</summary>
/// <param name="height">Non-negative bar heights.</param>
/// <returns>Total trapped water.</returns>
/// <example><c>RainWaterTwoPointers.Trap([4, 2, 0, 3, 2, 5])</c> returns <c>9</c>.
/// </example>
public static int Trap(int[] height)
{
if (height.Length == 0)
return 0; // 0 bars, so 0 water
// 0 is the first index. Length - 1 is the last index.
int left = 0, right = height.Length - 1;
int leftMax = height[left], rightMax = height[right];
int total = 0; // 0: no water counted yet
// Invariant: every bar outside left..right is settled and counted.
// leftMax and rightMax are the tallest bars seen from each side.
while (left < right)
{
if (leftMax <= rightMax)
{
left++; // +1: step the left pointer inward
leftMax = Math.Max(leftMax, height[left]);
// Water here is the wall height minus the bar. 0 if it is the wall.
total += leftMax - height[left];
}
else
{
right--; // -1: step the right pointer inward
rightMax = Math.Max(rightMax, height[right]);
total += rightMax - height[right];
}
}
return total;
}
}Math.Min(leftMax, rightMax) rule. Write the two-array version. Then say “I can drop the arrays with two pointers” and write that. The stack version is worth knowing too. It is the same machinery as the next problem, and it counts the water in a different shape.height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. At index 3 the bar of height 2 arrives. It pops the 0 at index 2. It finds index 1 underneath as the left wall. It adds width 1 × depth (Math.Min(1, 2) - 0) = 1. Later the bar of height 3 at index 7 pops a run of small bars. It adds the large middle basin. The layers add up to 6.
Reading the figure. The numbers under the bars are the heights. Each blue block is one layer of water. Its number is width times depth. A block appears when a taller bar arrives and pops a lower one. The wide block of 3 sits on top of a smaller one. A later pop can fill above an earlier layer.
< in the stack version keeps equal bars stacked, so no zero-depth basins are counted.int is 32-bit. With n up to 2·104 and heights up to 105, the total fits. For larger bounds, use long total.Given bar heights of width 1, find the area of the largest rectangle that fits inside the histogram.
Once you say “each bar is the height, and I need its left and right smaller walls”, the problem is done. Getting there is the interview.
0 at index n. It is shorter than every real bar. It drains the stack inside the loop and removes the cleanup block.public static class LargestRectangle
{
/// <summary>Area of the largest rectangle that fits under a histogram. Each bar
/// is tried as the limiting height. Its width runs between the nearest shorter
/// bar on each side, and one increasing stack finds both.</summary>
/// <param name="heights">Non-negative bar heights, each of width 1.</param>
/// <returns>The maximum rectangle area.</returns>
/// <example><c>LargestRectangle.Area([2, 1, 5, 6, 2, 3])</c> returns <c>10</c>.
/// </example>
public static int Area(int[] heights)
{
int n = heights.Length;
int best = 0; // 0: the empty rectangle, area 0
var stack = new Stack<int>(); // indices. Heights strictly increasing
// index runs 0..n. Index n is a sentinel bar of height 0. It is shorter
// than any bar, so it flushes the stack inside the loop.
// Invariant: each stacked bar is taller than the one below it.
for (int index = 0; index <= n; index++)
{
int bar = index == n ? 0 : heights[index];
// index is the nearest shorter-or-equal bar to the right of the top.
while (stack.Count > 0 && heights[stack.Peek()] >= bar)
{
int height = heights[stack.Pop()];
// Left wall: the new top is the nearest shorter bar to the left.
// + 1: the rectangle starts just past that shorter bar.
// 0: with an empty stack the rectangle reaches index 0.
int left = stack.Count > 0 ? stack.Peek() + 1 : 0;
// Width runs from left up to index - 1, so it is index - left.
best = Math.Max(best, height * (index - left));
}
stack.Push(index);
}
return best;
}
}heights = [2, 1, 5, 6, 2, 3]:
The winner is the 5 × 2 rectangle over the bars of height 5 and 6.
Reading the figure. The dashed green box is the winning rectangle. Its height comes from the bar of 5 (blue). The red bar is the nearest shorter bar on the left. It sits under the 5 on the stack. The amber bar is the nearest shorter bar on the right. Its arrival pops the 5. The width is the gap between the two walls.
public static class MaximalRectangle
{
/// <summary>Largest all-ones rectangle in a binary matrix. Treat each row as the
/// base of a histogram. Bar heights are the runs of ones stacked above that row.
/// Then it is Largest Rectangle, once per row.</summary>
/// <param name="matrix">Rows of '0' and '1' chars, all the same length.</param>
/// <returns>The area of the largest rectangle of ones.</returns>
/// <example><c>MaximalRectangle.Area([['1', '1'], ['1', '1']])</c> returns
/// <c>4</c>.</example>
public static int Area(char[][] matrix)
{
// matrix[0] is the first row. Length 0 there means no columns.
if (matrix.Length == 0 || matrix[0].Length == 0)
return 0; // 0: no cells, so no rectangle
// One bar per column. new int[] starts at 0: no ones yet.
var heights = new int[matrix[0].Length];
int best = 0; // 0: no rectangle found yet
// Invariant: heights[c] = run of '1' cells ending at this row in column c.
foreach (char[] row in matrix)
{
// c is the column. 0: start at the left edge.
for (int c = 0; c < row.Length; c++)
// + 1 extends the run by this cell. 0 resets it on a '0' cell.
heights[c] = row[c] == '1' ? heights[c] + 1 : 0;
best = Math.Max(best, LargestRectangle.Area(heights));
}
return best;
}
}A Hard problem that shrinks to a few lines once you own the histogram routine. This is why the histogram problem gets asked at all. LargestRectangle.Area only reads heights, so reusing one array across rows is safe.
h × n.0.>= rather than > pops equal bars early with a short width. That is safe. The leftmost of the equal run is popped last and gets the full width.height * width is an int product. At LeetCode bounds (104 × 105) it fits. For larger bounds, cast to long first.Stack<int>, so distances and widths stay computable.while.n drains the stack inside the loop and removes the cleanup branch.Pattern 15, Topological Sort, moves back to graphs. It is the ordering algorithm that BFS and DFS both hint at. It is the standard answer to any question about dependencies.