Top Stack Interview Questions & Monotonic Stack Patterns (2026)

1. Introduction to Stack Patterns

A Stack operates under the LIFO (Last In, First Out) principle. In technical interviews, Stacks appear across four primary problem patterns:

1. Parentheses & Matching Delimiters: Validating matching brackets and nested scopes.
2. Monotonic Stack Pattern: Finding the Next Greater/Smaller Element in O(N) time.
3. Min / Max Auxiliary Tracking: Maintaining running extrema in O(1) query time.
4. Expression Evaluation & Infix/Postfix Parsing: Calculator engines and AST parsers.

2. Core Stack Interview Questions & Verified Solutions

Q1. Valid Parentheses (Matching Delimiters Pattern)

Problem Statement: Given a string s containing only '(', ')', '{', '}', '[', and ']', determine if the input string is valid.

python
def isValid(s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in bracket_map:
            # Closing bracket
            top_element = stack.pop() if stack else '#'
            if bracket_map[char] != top_element:
                return False
        else:
            # Opening bracket
            stack.append(char)
            
    return len(stack) == 0

• Time Complexity: O(N) | Space Complexity: O(N)

Q2. Min Stack Design (O(1) Min Retrieval)

Problem Statement: Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) constant time.

cpp
#include <stack>
#include <algorithm>

class MinStack {
private:
    std::stack<int> mainStack;
    std::stack<int> minStack;

public:
    MinStack() {}

    void push(int val) {
        mainStack.push(val);
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        }
    }

    void pop() {
        if (mainStack.top() == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
    }

    int top() {
        return mainStack.top();
    }

    int getMin() {
        return minStack.top();
    }
};

• Time Complexity: All operations O(1) | Space Complexity: O(N)

Q3. Next Greater Element (Monotonic Decreasing Stack)

Problem Statement: Given an array nums, find the next greater element for every element. If no greater element exists, output -1.

java
import java.util.*;

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    
    Stack<Integer> stack = new Stack<>(); // Stores indices
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int prevIdx = stack.pop();
            result[prevIdx] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

• Time Complexity: O(N) (Each element is pushed and popped at most once) | Space Complexity: O(N)

Q4. Daily Temperatures

Problem Statement: Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^{th} day to get a warmer temperature.

python
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    ans = [0] * n
    stack = [] # Stores indices: [(temp, index)]
    
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            ans[prev_idx] = i - prev_idx
        stack.append(i)
        
    return ans

• Time Complexity: O(N) | Space Complexity: O(N)

Q5. Largest Rectangle in Histogram (Advanced Monotonic Stack)

Problem Statement: Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

javascript
function largestRectangleArea(heights) {
    const stack = []; // Stores indices
    let maxArea = 0;
    const n = heights.length;

    for (let i = 0; i <= n; i++) {
        const currentHeight = (i === n) ? 0 : heights[i];

        while (stack.length > 0 && currentHeight < heights[stack[stack.length - 1]]) {
            const h = heights[stack.pop()];
            const width = (stack.length === 0) ? i : (i - stack[stack.length - 1] - 1);
            maxArea = Math.max(maxArea, h * width);
        }
        stack.push(i);
    }
    return maxArea;
}

• Time Complexity: O(N) | Space Complexity: O(N)

3. Monotonic Stack Cheat Sheet

Practice all 500+ curated stack questions on DSAMaster's practice platform.