Stack interview questions

A stack remembers things in the order you will need to undo them. Whenever the most recent unresolved item is the one you must deal with next, you are looking at a stack problem.

How do I solve stack interview questions?

A stack handles problems where the latest unresolved item must be handled first: matching brackets, evaluating expressions, undoing steps and finding the next greater or smaller element. A monotonic stack keeps its items ordered, so each element is pushed and popped once and the whole pass is linear.

Practise stack

How to recognise a stack problem

Nested or matching structure: brackets, tags, parentheses in an expression, a path with .. segments.

You must find, for each element, the next greater or smaller element, or how long until a warmer day.

Something must be undone in reverse order, or a recursive solution needs an explicit stack to avoid deep recursion.

How to build the solution

For matching, push opening items and, on a closing item, check the top matches and pop. At the end the stack must be empty.

For next-greater problems, keep a stack of indexes whose answer is not yet known, in decreasing order of value. When a new element is larger than the top, pop and record the answer, repeating until it is not larger, then push the new index.

Evaluate expressions with two stacks (numbers and operators) or convert to postfix and evaluate with one.

Each element is pushed once and popped at most once, so the cost is linear, even with a loop inside the loop.

Classic problems to practise

Valid Parentheses, Min Stack, Daily Temperatures, Next Greater Element, Evaluate Reverse Polish Notation, Generate Parentheses, Largest Rectangle in Histogram, Decode String.

Mistakes interviewers see

Popping from an empty stack. Check before you look at the top, and decide what an unmatched closing item means.

Forgetting to check that the stack is empty at the end, which accepts input with unclosed openers.

Storing values when you need indexes, so you cannot compute distances or widths.

Confusing the order of the monotonic stack (increasing or decreasing) with what the problem asks for.

Practise it as an interview

Take a topic-based interview on stack to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.

Frequently asked questions

What is a monotonic stack?

A stack whose items stay in sorted order, because you pop everything that would break the order before pushing. It finds next greater or smaller elements in linear time.

Can recursion replace a stack?

Yes, recursion uses the call stack. An explicit stack avoids recursion depth limits and makes the state visible, which interviewers sometimes ask for.