Category 5: Stacks & Queues — 15 Problems

THEORY

Core Concepts & Patterns

Stacks and queues are fundamental linear data structures that enforce specific ordering semantics. Understanding their properties and recognizing problem patterns is essential for efficient algorithm design.

Stack (LIFO - Last In First Out)

A stack restricts insertion and deletion to one end (the top). Common operations:

1

Push(T) — Add element to top. O(1) time.

2

Pop() — Remove and return top element. O(1) time. Throws if empty.

3

Peek() — Return top element without removing. O(1) time.

4

IsEmpty() — Check if stack contains no elements. O(1) time.

Queue (FIFO - First In First Out)

A queue restricts insertion at one end (rear) and deletion at the other (front). Common operations:

1

Enqueue(T) — Add element to rear. O(1) amortized time.

2

Dequeue() — Remove and return front element. O(1) amortized time. Throws if empty.

3

Peek() — Return front element without removing. O(1) time.

4

IsEmpty() — Check if queue contains no elements. O(1) time.

Monotonic Stack Pattern

A powerful technique for finding the next/previous greater/smaller element in O(n) time. Maintains a stack of indices in either increasing or decreasing order.

💡

Key insight: When iterating through elements, popping from the stack establishes relationships (e.g., current element is the next greater for all popped elements). This single-pass O(n) approach beats naive O(n²) comparisons.

Stack for Expression Evaluation

Stacks excel at evaluating expressions where operator precedence or parentheses create nesting. Two common approaches:

Reverse Polish Notation (RPN): Operators follow operands. Stack processes operands, pushes operators' results.
Infix notation: Traditional form. Use two stacks (operators and operands) or convert to postfix via shunting-yard algorithm.

Stack for Bracket Matching

Parentheses, braces, and brackets matching is a canonical stack application. Push opening brackets; when closing bracket encountered, check if it matches the top of the stack.

Two-Stack Simulation

Queues can be implemented using two stacks: one for enqueue, one for dequeue. Amortized O(1) per operation by batch-transferring elements during dequeue.

Problem 1: Brackets

Given a string of brackets: (, [, {, ), ], }. Determine if brackets are properly matched and nested.

Stack Matching Codility ★★

1

Problem Statement

A string consisting of characters: (, [, {, ), ], }. Return 1 if all brackets are properly matched and correctly nested, 0 otherwise.

Approach

1

Use a stack to track opening brackets.

2

For each character: if opening, push to stack; if closing, check if it matches the top of stack.

3

At end, stack must be empty for valid nesting.

4

If any mismatch or unmatched brackets, return 0. Else return 1.

C# Implementation

csharp

public int Solution(string S)
{
    Stack<char> stack = new Stack<char>();

    foreach (char c in S)
    {
        if (c == '(' || c == '[' || c == '{')
        {
            stack.Push(c);
        }
        else
        {
            if (stack.Count == 0) return 0;

            char top = stack.Pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
            {
                return 0;
            }
        }
    }

    return stack.Count == 0 ? 1 : 0;
}

Trace Example

Input: "({[]})"

Char	Type	Stack	Action
(	Open	(	Push (
{	Open	( {	Push {
[	Open	( { [	Push [
]	Close	( {	Pop [, matches
}	Close	(	Pop {, matches
)	Close	empty	Pop (, matches
End	—	empty	Return 1

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Empty string → return 1 (vacuously true)
Single closing bracket → return 0
Mismatched types: "{)" → return 0
Extra opening: "((" → return 0

Problem 2: Nesting

Check if a string of parentheses is properly nested (can be arbitrary depth, but each ) must match a preceding ().

Stack Matching Codility ★★

2

Problem Statement

A string of only ( and ) characters. Proper nesting means: each ) has a matching (, and no ) appears before its corresponding (.

Approach

Track the balance of open parentheses. Increment on (, decrement on ). Balance must never go negative, and must end at 0.

C# Implementation

csharp

public int Solution(string S)
{
    int balance = 0;

    foreach (char c in S)
    {
        if (c == '(')
        {
            balance++;
        }
        else // c == ')'
        {
            balance--;
            if (balance < 0) return 0;
        }
    }

    return balance == 0 ? 1 : 0;
}

Trace Example

Input: "(()(()()))"

Char	Balance	Valid
(	1	✓
(	2	✓
)	1	✓
(	2	✓
(	3	✓
)	2	✓
(	3	✓
)	2	✓
)	1	✓
)	0	✓
End	0	Return 1

Time Complexity

O(n)

Space Complexity

O(1)

Edge Cases

Empty string → return 1
Starts with closing: ")()" → return 0 (balance goes negative)
Unclosed: "(()" → return 0 (balance != 0 at end)

Problem 3: StoneWall

Build a wall with the minimum number of stone blocks. A stone can be placed at any height on top of the wall so far.

Stack Height Tracking Codility ★★★

3

Problem Statement

Given array H where H[i] is the required height at position i. Each stone placed must have maximum height H[j] for some j. Stones cannot extend beyond position i. Find the minimum number of stones needed.

Approach

Use a stack to maintain heights. When height increases, push. When height decreases, pop and count. When heights are equal at different positions, we can reuse stone layers.

C# Implementation

csharp

public int Solution(int[] H)
{
    Stack<int> stack = new Stack<int>();
    int stones = 0;

    foreach (int height in H)
    {
        while (stack.Count > 0 && stack.Peek() > height)
        {
            stack.Pop();
            stones++;
        }

        if (stack.Count == 0 || stack.Peek() < height)
        {
            stack.Push(height);
        }
    }

    stones += stack.Count;
    return stones;
}

Trace Example

Input: H = [8, 8, 5, 7, 1, 7, 1, 4, 2]

i	H[i]	Stack	Stones Added	Total
0	8	[8]	0	0
1	8	[8]	0	0
2	5	[5]	1 (pop 8)	1
3	7	[5, 7]	0	1
4	1	[1]	2 (pop 7, 5)	3
5	7	[1, 7]	0	3
6	1	[1]	1 (pop 7)	4
7	4	[1, 4]	0	4
8	2	[1, 2]	0	4
End	—	—	2 (stack count)	6

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

All same height: [5, 5, 5] → 1 stone
Monotonic increasing: [1, 2, 3] → 3 stones
Monotonic decreasing: [3, 2, 1] → 3 stones

Problem 4: Fish

Fish swimming in a stream. A fish eats another if they swim toward each other and the first is bigger. Count survivors.

Stack Simulation Codility ★★★

4

Problem Statement

Fish[i] is the size, Direction[i] is 0 (upstream) or 1 (downstream). Fish moving in opposite directions collide. Larger fish eats smaller. Fish moving same direction never collide. Count survivors.

Approach

Use stack to track downstream fish. When encountering upstream fish, it eats downstream fish until no more or meets a larger downstream fish.

C# Implementation

csharp

public int Solution(int[] A, int[] B)
{
    Stack<int> downstream = new Stack<int>();
    int alive = 0;

    foreach (int i = 0; i < A.Length; i++)
    {
        int fish = A[i];
        int dir = B[i];
        bool eaten = false;

        if (dir == 1) // downstream
        {
            downstream.Push(fish);
        }
        else // dir == 0, upstream
        {
            while (downstream.Count > 0 && !eaten)
            {
                int top = downstream.Pop();
                if (top > fish)
                {
                    downstream.Push(top);
                    eaten = true;
                }
            }
        }

        if (!eaten)
        {
            alive++;
        }
    }

    alive += downstream.Count;
    return alive;
}

Trace Example

Input: A = [4, 3, 2, 1, 5], B = [0, 1, 0, 0, 0] (0=upstream, 1=downstream)

i	Fish	Dir	Action	Downstream	Alive
0	4	0	Upstream, no collide	[]	1
1	3	1	Downstream, push	[3]	1
2	2	0	Upstream, eats 3	[]	2
3	1	0	Upstream, no collide	[]	3
4	5	0	Upstream, no collide	[]	4
End	—	—	Count stack	[]	4

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

All downstream: [1, 2, 3], [1, 1, 1] → 3 survivors
All upstream: [1, 2, 3], [0, 0, 0] → 3 survivors
Alternating: [1, 2, 1], [1, 0, 1] → 2 survivors (1st: 1d, eaten by 2u; 2nd: 2u survives; 3rd: 1d survives)

Problem 5: Valid Parentheses

Classic LeetCode problem. Given string with (){}[], determine if valid.

Stack Matching LeetCode 20 ★

5

Problem Statement

Given string containing just characters (){}[]. Determine if input string is valid: all brackets must be closed by the same type, and brackets must be closed in correct order.

Approach

Use dictionary to map closing brackets to opening brackets. Push opening brackets; pop and match on closing brackets.

C# Implementation

csharp

public bool IsValid(string s)
{
    Dictionary<char, char> pairs = new Dictionary<char, char>
    {
        { ')', '(' },
        { ']', '[' },
        { '}', '{' }
    };

    Stack<char> stack = new Stack<char>();

    foreach (char c in s)
    {
        if (pairs.ContainsKey(c))
        {
            if (stack.Count == 0 || stack.Pop() != pairs[c])
                return false;
        }
        else
        {
            stack.Push(c);
        }
    }

    return stack.Count == 0;
}

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Empty string → true
Single character → false
Mismatched: "([)]" → false
Extra closing: "([)]" → false

Problem 6: Min Stack

Design a stack with O(1) push, pop, top, and getMin operations.

Stack Design LeetCode 155 ★★

6

Problem Statement

Implement MinStack class supporting push(val), pop(), top(), and getMin() in O(1) time.

Approach

Use two stacks: one for values, one for minimum values. Sync pushes and pops.

C# Implementation

csharp

public class MinStack
{
    private Stack<int> stack;
    private Stack<int> minStack;

    public MinStack()
    {
        stack = new Stack<int>();
        minStack = new Stack<int>();
    }

    public void Push(int val)
    {
        stack.Push(val);
        int min = minStack.Count == 0 ? val : Math.Min(minStack.Peek(), val);
        minStack.Push(min);
    }

    public void Pop()
    {
        stack.Pop();
        minStack.Pop();
    }

    public int Top()
    {
        return stack.Peek();
    }

    public int GetMin()
    {
        return minStack.Peek();
    }
}

Trace Example

Operations: push(3), push(1), push(2), getMin(), pop(), getMin()

Op	Stack	MinStack	Result
push(3)	[3]	[3]	—
push(1)	[3, 1]	[3, 1]	—
push(2)	[3, 1, 2]	[3, 1, 1]	—
getMin()	[3, 1, 2]	[3, 1, 1]	1
pop()	[3, 1]	[3, 1]	—
getMin()	[3, 1]	[3, 1]	1

Push/Pop Time

O(1)

Space Complexity

O(n)

Edge Cases

Duplicate values: push(1), push(1), getMin() → 1
Negative numbers: push(-1), push(-2), getMin() → -2

Problem 7: Daily Temperatures

Given array of daily temperatures, return array where each element is days until warmer temperature.

Monotonic Stack LeetCode 739 ★★

7

Problem Statement

Given temperatures[i], for each day, find number of days until a warmer day. Return answer array where answer[i] is the days to wait. If no warmer day, answer[i] = 0.

Approach

Use monotonic decreasing stack of indices. Iterate from right to left. When current temp > stack top temp, pop and record distance. Push current index.

C# Implementation

csharp

public int[] DailyTemperatures(int[] temperatures)
{
    int n = temperatures.Length;
    int[] answer = new int[n];
    Stack<int> stack = new Stack<int>();

    for (int i = n - 1; i >= 0; i--)
    {
        while (stack.Count > 0 && temperatures[i] >= temperatures[stack.Peek()])
        {
            stack.Pop();
        }

        if (stack.Count > 0)
        {
            answer[i] = stack.Peek() - i;
        }

        stack.Push(i);
    }

    return answer;
}

Trace Example

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

i	Temp	Stack (indices)	Answer[i]
7	73	[7]	0
6	76	[6]	0
5	72	[6, 5]	1 (6-5)
4	69	[6, 5, 4]	1 (5-4)
3	71	[6, 5, 3]	2 (5-3)
2	75	[6, 2]	4 (6-2)
1	74	[6, 2, 1]	1 (2-1)
0	73	[6, 2, 1, 0]	1 (1-0)

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Monotonic decreasing: [5, 4, 3, 2, 1] → [0, 0, 0, 0, 0]
Monotonic increasing: [1, 2, 3, 4, 5] → [1, 1, 1, 1, 0]

Problem 8: Next Greater Element I

Given two arrays nums1 and nums2, for each element in nums1, find its next greater element in nums2.

Monotonic Stack LeetCode 496 ★

8

Problem Statement

nums1 is a subset of nums2 (all unique). For each nums1[i], find the next greater element in nums2 (in order). Return result array or -1 if no greater element.

Approach

Build map from element to next greater using monotonic stack on nums2. Then lookup each nums1 element in the map.

C# Implementation

csharp

public int[] NextGreaterElement(int[] nums1, int[] nums2)
{
    Dictionary<int, int> map = new Dictionary<int, int>();
    Stack<int> stack = new Stack<int>();

    // Build map: element -> next greater
    foreach (int num in nums2)
    {
        while (stack.Count > 0 && stack.Peek() < num)
        {
            map[stack.Pop()] = num;
        }
        stack.Push(num);
    }

    int[] result = new int[nums1.Length];
    for (int i = 0; i < nums1.Length; i++)
    {
        result[i] = map.ContainsKey(nums1[i]) ? map[nums1[i]] : -1;
    }

    return result;
}

Trace Example

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Process nums2	Stack	Map
num=1	[1]	{}
num=3 (>1)	[3]	{1: 3}
num=4 (>3)	[4]	{1: 3, 3: 4}
num=2 (<4)	[4, 2]	{1: 3, 3: 4}
nums1[0]=4: map[4] undefined → -1
nums1[1]=1: map[1]=3
nums1[2]=2: map[2] undefined → -1

Time Complexity

O(n + m)

Space Complexity

O(m)

Edge Cases

No greater elements: nums1=[2,4], nums2=[1,2,3,4] → [-1, -1]
Single element: nums1=[1], nums2=[1,2] → [2]

Problem 9: Evaluate Reverse Polish Notation

Evaluate an expression in RPN (postfix) format where operators follow operands.

Stack Evaluation LeetCode 150 ★★

9

Problem Statement

Given array of strings tokens representing RPN expression. Operators are +, -, *, /. Evaluate and return result. Integer division truncates toward zero.

Approach

Push operands onto stack. On operator, pop two operands, apply operator, push result. Final stack top is answer.

C# Implementation

csharp

public int EvalRPN(string[] tokens)
{
    Stack<long> stack = new Stack<long>();

    foreach (string token in tokens)
    {
        if (token == "+" || token == "-" || token == "*" || token == "/")
        {
            long b = stack.Pop();
            long a = stack.Pop();

            switch (token)
            {
                case "+": stack.Push(a + b); break;
                case "-": stack.Push(a - b); break;
                case "*": stack.Push(a * b); break;
                case "/": stack.Push(a / b); break;
            }
        }
        else
        {
            stack.Push(long.Parse(token));
        }
    }

    return (int)stack.Pop();
}

Trace Example

Input: tokens = ["2","1","+","3","*"] which is (2+1)*3 = 9

Token	Type	Stack	Action
2	Operand	[2]	Push
1	Operand	[2, 1]	Push
+	Op	[3]	Pop 1,2; Push 2+1
3	Operand	[3, 3]	Push
*	Op	[9]	Pop 3,3; Push 3*3

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Single operand: ["42"] → 42
Negative division: ["6","4","/"] → 1 (truncate toward zero)
Complex nesting: ["15","7","1","1","+","-","/","3","*","2","1","1","+","+","-"] → 5

Problem 10: Largest Rectangle in Histogram

Given array of heights, find the area of the largest rectangle that can be formed.

Monotonic Stack LeetCode 84 ★★★

10

Problem Statement

Given heights array representing histogram bars. Calculate maximum rectangular area that can fit in the histogram.

Approach

Use monotonic increasing stack of indices. When height decreases, pop from stack and calculate area for each popped bar. The width extends from current position back to the index before the remaining top of stack.

C# Implementation

csharp

public int LargestRectangleArea(int[] heights)
{
    Stack<int> stack = new Stack<int>();
    int maxArea = 0;

    for (int i = 0; i < heights.Length; i++)
    {
        while (stack.Count > 0 && heights[stack.Peek()] > heights[i])
        {
            int h = heights[stack.Pop()];
            int w = stack.Count == 0 ? i : i - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, h * w);
        }
        stack.Push(i);
    }

    while (stack.Count > 0)
    {
        int h = heights[stack.Pop()];
        int w = stack.Count == 0 ? heights.Length : heights.Length - stack.Peek() - 1;
        maxArea = Math.Max(maxArea, h * w);
    }

    return maxArea;
}

Trace Example

Input: heights = [2, 1, 5, 6, 2, 3]

i	h[i]	Stack	Calc Area	MaxArea
0	2	[0]	—	0
1	1	[1]	2*1=2 (pop 0)	2
2	5	[1, 2]	—	2
3	6	[1, 2, 3]	—	2
4	2	[1, 4]	61=6, 52=10 (pop 3,2)	10
5	3	[1, 4, 5]	—	10
End	—	—	31=3, 25=10, 1*6=6	10

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Single bar: [5] → 5
Monotonic increasing: [1, 2, 3, 4, 5] → 9 (height 4, width 2)
All same: [5, 5, 5] → 15

Problem 11: Implement Queue using Stacks

Implement a queue using two stacks with amortized O(1) operations.

Stack Design LeetCode 232 ★

11

Problem Statement

Implement MyQueue class with push(x), pop(), peek(), and empty() using only two stacks. Operations should have amortized O(1) time.

Approach

Use stack1 for enqueue operations, stack2 for dequeue. When dequeueing and stack2 is empty, transfer all from stack1 to stack2 (reverse order).

C# Implementation

csharp

public class MyQueue
{
    private Stack<int> s1;
    private Stack<int> s2;

    public MyQueue()
    {
        s1 = new Stack<int>();
        s2 = new Stack<int>();
    }

    public void Push(int x)
    {
        s1.Push(x);
    }

    public int Pop()
    {
        Peek();
        return s2.Pop();
    }

    public int Peek()
    {
        if (s2.Count == 0)
        {
            while (s1.Count > 0)
            {
                s2.Push(s1.Pop());
            }
        }
        return s2.Peek();
    }

    public bool Empty()
    {
        return s1.Count == 0 && s2.Count == 0;
    }
}

Trace Example

Operations: push(1), push(2), pop(), push(3), peek()

Op	S1	S2	Result
push(1)	[1]	[]	—
push(2)	[1,2]	[]	—
pop()	[]	[2]	Return 1
push(3)	[3]	[2]	—
peek()	[3]	[2]	Return 2

Push Time

O(1)

Pop Amortized

O(1)

Space Complexity

O(n)

Edge Cases

All push: push(1), push(2), empty() → false
Empty check: pop on empty → Exception

Problem 12: Decode String

Decode string with pattern k[encoded_string] where k is a number multiplying the string inside brackets.

Nested Brackets LeetCode 394 ★★

12

Problem Statement

String pattern: k[encoded_string] where k is a positive integer, brackets can be nested. Decode the string. Example: "3[a2[c]]" = "accaccacc".

Approach

Use stack to track characters and numbers. On closing bracket, pop characters, pop number, repeat characters, push back. On opening bracket, push it for grouping.

C# Implementation

csharp

public string DecodeString(string s)
{
    Stack<object> stack = new Stack<object>();
    int num = 0;
    StringBuilder sb = new StringBuilder();

    foreach (char c in s)
    {
        if (char.IsDigit(c))
        {
            num = num * 10 + (int)(c - '0');
        }
        else if (c == '[')
        {
            stack.Push(sb.ToString());
            stack.Push(num);
            sb = new StringBuilder();
            num = 0;
        }
        else if (c == ']')
        {
            int k = (int)stack.Pop();
            string prev = ((string)stack.Pop());
            string decoded = "";
            for (int i = 0; i < k; i++)
            {
                decoded += sb.ToString();
            }
            sb = new StringBuilder(prev + decoded);
        }
        else
        {
            sb.Append(c);
        }
    }

    return sb.ToString();
}

Trace Example

Input: "3[a2[c]]"

Char	Action	Stack	SB	Num
3	Digit	[]		3
[	Open	["", 3]		0
a	Char	["", 3]	a	0
2	Digit	["", 3]	a	2
[	Open	["", 3, "a", 2]		0
c	Char	["", 3, "a", 2]	c	0
]	Close	["", 3]	acc	0
]	Close	[]	accaccacc	0

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

No brackets: "abc" → "abc"
Nested multiple levels: "2[abc]3[cd]ef" → "abcabccdcdcdef"
Multi-digit number: "10[a]" → "aaaaaaaaaa"

Problem 13: Basic Calculator II

Evaluate expression string with +, -, *, / (no parentheses, operator precedence applies).

Expression Evaluation LeetCode 227 ★★

13

Problem Statement

Given string expression with +, -, *, /. No parentheses. Evaluate respecting operator precedence. Integer division truncates toward zero.

Approach

Use stack. For +/-, push operand/negative. For *,/, pop, apply, push result. Finally sum all in stack.

C# Implementation

csharp

public int Calculate(string s)
{
    Stack<long> stack = new Stack<long>();
    long num = 0;
    char op = '+';

    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];

        if (char.IsDigit(c))
        {
            num = num * 10 + (c - '0');
        }

        if (!char.IsDigit(c) && c != ' ' || i == s.Length - 1)
        {
            switch (op)
            {
                case '+': stack.Push(num); break;
                case '-': stack.Push(-num); break;
                case '*': stack.Push(stack.Pop() * num); break;
                case '/': stack.Push(stack.Pop() / num); break;
            }
            op = c;
            num = 0;
        }
    }

    long result = 0;
    while (stack.Count > 0)
    {
        result += stack.Pop();
    }

    return (int)result;
}

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Spaces: " 3+5 / 2" → 4
Negative division: "6/2" → 3
Single digit: "42" → 42

Problem 14: Asteroid Collision

Asteroids on a line collide if moving toward each other. Right-moving in stack, left-moving collide with them.

Stack Simulation LeetCode 735 ★★

14

Problem Statement

Asteroids represented by int array. Positive = moving right, negative = moving left. If two collide, smaller explodes. Return list of surviving asteroids.

Approach

Use stack to track right-moving asteroids. For each left-moving, collide with stack top. Survivors added to stack or result.

C# Implementation

csharp

public int[] AsteroidCollision(int[] asteroids)
{
    Stack<int> stack = new Stack<int>();

    foreach (int ast in asteroids)
    {
        bool alive = true;

        while (alive && ast < 0 && stack.Count > 0 && stack.Peek() > 0)
        {
            int top = stack.Pop();
            if (top < -ast)
            {
                // top explodes, ast continues
            }
            else if (top == -ast)
            {
                // both explode
                alive = false;
            }
            else
            {
                // ast explodes, top survives
                alive = false;
                stack.Push(top);
            }
        }

        if (alive)
        {
            stack.Push(ast);
        }
    }

    return stack.ToArray();
}

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

All right: [5, 10, -5] → [5, 10] (can't catch up)
Head-on: [1, 2, -1, -2] → [-2] (all but last collide)
Same size: [1, -1] → [] (both explode)

Problem 15: Trapping Rain Water

Given elevation map, calculate how much rainwater can be trapped after raining. Stack-based approach.

Monotonic Stack LeetCode 42 ★★★

15

Problem Statement

Given array height representing elevation map. Calculate total water trapped after it rains.

Approach (Stack-based)

Use monotonic decreasing stack of indices. When height increases, pop bars and calculate trapped water between them. Water depth = min(current, popped) - empty space height.

C# Implementation

csharp

public int Trap(int[] height)
{
    Stack<int> stack = new Stack<int>();
    int water = 0;

    for (int i = 0; i < height.Length; i++)
    {
        while (stack.Count > 0 && height[i] > height[stack.Peek()])
        {
            int top = stack.Pop();
            if (stack.Count == 0) break;

            int left = stack.Peek();
            int w = i - left - 1;
            int h = Math.Min(height[i], height[left]) - height[top];
            water += w * h;
        }
        stack.Push(i);
    }

    return water;
}

Trace Example

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Expected: 6 units of water trapped.

💡

Visualization: Stack maintains indices of decreasing heights. When we find a taller bar, trapped water is calculated by popping valleys. Width × depth calculations accumulate total trapped water.

Time Complexity

O(n)

Space Complexity

O(n)

Edge Cases

Flat: [5, 5, 5] → 0
Decreasing: [5, 4, 3] → 0
Valley: [3, 0, 2] → 2 (width 1, height 2)