Skip to content

08. Stack#

Problems at a glance#

LC Problem
225 Implement Stack using Queues ↗
20 Valid Parentheses ↗
227 Basic Calculator II ↗
150 Evaluate Reverse Polish Notation ↗
503 Next Greater Element II ↗
739 Daily Temperatures ↗
1762 Buildings With an Ocean View ↗
456 132 Pattern ↗
735 Asteroid Collision ↗
155 Min Stack ↗
224 Basic Calculator ↗
42 Trapping Rain Water ↗
84 Largest Rectangle in Histogram ↗
1944 Number of Visible People in a Queue ↗

Problem 1: Implement Stack using Queues (Leetcode:225)#

Problem Statement

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.
  • int pop() Removes the element on the top of the stack and returns it.
  • int top() Returns the element on the top of the stack.
  • boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

  • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 2, 2, false]
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2); myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, top, and empty.
  • All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        # Move all elements from q1 to q2, push x, swap back
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0
Explanation:

  1. Keep two queues; q1 always holds the stack contents with the newest element at the front (queue head).
  2. On push(x): append x to empty q2, then dequeue every element from q1 into q2, then swap the queue references.
  3. After rotation, the most recently pushed value sits at the front of q1, so pop/top are O(1) queue operations.
  4. empty checks whether q1 has any elements.

Time: push O(n), pop/top/empty O(1)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # Rotate so the newest element moves to the front
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0
Explanation:

  1. Use a single queue and maintain LIFO order by rotating after every push.
  2. Append the new value to the back, then move size - 1 elements from front to back.
  3. The front of the queue always holds the stack top, so pop and top read from the front.
  4. This satisfies the follow-up of implementing a stack with one queue only.

Time: push O(n), pop/top/empty O(1)  |  Space: O(n)

Problem 2: Valid Parentheses (Leetcode:20)#

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([])"
Output: true

Example 5:

Input: s = "([)]"
Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {')': '(', '}': '{', ']': '['}

        for ch in s:
            if ch in pairs:
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                stack.append(ch)

        return not stack
Explanation:

  1. Use a stack to store unmatched opening brackets in order of appearance.
  2. Map each closing bracket to its required opening partner.
  3. On a closing bracket, pop the stack and verify the types match; an empty stack means no partner.
  4. After scanning, validity requires the stack to be empty (all brackets closed).

Time: O(n)  |  Space: O(n)

1
2
3
4
5
class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()', '').replace('[]', '').replace('{}', '')
        return s == ''
Explanation:

  1. Repeatedly remove every adjacent valid pair (), [], or {} from the string.
  2. Valid nesting always reduces to empty string after all inner pairs are eliminated.
  3. If any characters remain, some bracket was unmatched or out of order.
  4. Simple brute-force alternative; no explicit stack, but models the same LIFO cancellation idea.

Time: O(n²) worst case  |  Space: O(n)

Problem 3: Basic Calculator II(Leetcode:227)#

Problem Statement

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note:
You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

  • 1 <= s.length <= 3 * 10^5
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 231 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        sign = '+'

        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            if ch in '+-*/' or i == len(s) - 1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop() * num)
                else:
                    stack.append(int(stack.pop() / num))
                sign = ch
                num = 0

        return sum(stack)
Explanation:

  1. Defer addition/subtraction by pushing signed terms onto a stack.
  2. When reading * or /, immediately combine with the previous stack top (higher precedence).
  3. Each number is fully parsed before applying the operator that preceded it.
  4. Final answer is the sum of all stack entries — only addition remains.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def calculate(self, s: str) -> int:
        res = 0
        prev = 0
        curr = 0
        op = '+'

        for i, ch in enumerate(s):
            if ch.isdigit():
                curr = curr * 10 + int(ch)
            if ch in '+-*/' or i == len(s) - 1:
                if op in '+-':
                    res += prev
                    prev = curr if op == '+' else -curr
                elif op == '*':
                    prev *= curr
                else:
                    prev = int(prev / curr)
                op = ch
                curr = 0

        return res + prev
Explanation:

  1. Track a running total (res) and the last evaluated term (prev).
  2. On +/-, flush prev into res and start a new signed term.
  3. On *//, update prev in place without touching res.
  4. Same operator-precedence logic as the stack approach, but uses O(1) extra space.

Time: O(n)  |  Space: O(1)

Problem 4: Evaluate Reverse Polish Notation (Leetcode:150)#

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

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

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        ops = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a / b),
        }

        for tok in tokens:
            if tok in ops:
                b, a = stack.pop(), stack.pop()
                stack.append(ops[tok](a, b))
            else:
                stack.append(int(tok))

        return stack[0]
Explanation:

  1. Scan tokens left to right — the natural evaluation order for postfix notation.
  2. Push operands onto the stack.
  3. On an operator, pop two operands (second popped is the left operand), compute, push result.
  4. A valid expression ends with exactly one value on the stack.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        def evaluate(i: int) -> tuple[int, int]:
            tok = tokens[i]
            if tok not in '+-*/':
                return int(tok), i - 1
            right, j = evaluate(i - 1)
            left, j = evaluate(j)
            if tok == '+':
                return left + right, j
            if tok == '-':
                return left - right, j
            if tok == '*':
                return left * right, j
            return int(left / right), j

        result, _ = evaluate(len(tokens) - 1)
        return result
Explanation:

  1. Parse from the last token recursively — postfix trees are evaluated bottom-up from the right.
  2. Each operator recursively evaluates its right subtree first, then its left subtree.
  3. Returns both the computed value and the next index to process.
  4. Same logic as the stack, expressed as recursion instead of an explicit stack.

Time: O(n)  |  Space: O(n) recursion depth

Problem 5: Next Greater Element II (Leetcode:503)#

Problem Statement

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number.
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

Input: nums = [2,1,3,4,3]
Output: [3,3,4,-1,4]

Constraints:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = [-1] * n
        stack = []  # indices with unresolved next greater

        for i in range(2 * n):
            while stack and nums[stack[-1]] < nums[i % n]:
                res[stack.pop()] = nums[i % n]
            if i < n:
                stack.append(i)

        return res
Explanation:

  1. Simulate a circular array by iterating 2 * n times with index i % n.
  2. Maintain a monotonic decreasing stack of indices waiting for a greater element.
  3. When a larger value appears, pop and assign it as the next greater for those indices.
  4. Only push indices during the first pass (i < n) to avoid duplicate processing.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = [-1] * n

        for i in range(n):
            for j in range(i + 1, i + n):
                if nums[j % n] > nums[i]:
                    res[i] = nums[j % n]
                    break

        return res
Explanation:

  1. For each index, scan forward circularly up to n - 1 steps.
  2. The first element strictly greater than nums[i] is the answer.
  3. If no greater element exists in the full circle, leave -1.
  4. Straightforward brute force; easy to reason about but slower on large inputs.

Time: O(n²)  |  Space: O(1) excluding output

Problem 6: Daily Temperatures (Leetcode:739)#

Problem Statement

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        res = [0] * n
        stack = []  # indices, monotonic decreasing by temperature

        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                j = stack.pop()
                res[j] = i - j
            stack.append(i)

        return res
Explanation:

  1. Stack stores indices of days still waiting for a warmer day.
  2. When a warmer temperature arrives, pop all colder days and set their wait distance.
  3. Push the current index; colder days stay on the stack for future resolution.
  4. Classic monotonic stack — each index is pushed and popped at most once.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        res = [0] * n

        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    res[i] = j - i
                    break

        return res
Explanation:

  1. For each day, scan every future day until a warmer one is found.
  2. Record the index difference as the wait time.
  3. If the inner loop finishes without finding warmth, res[i] stays 0.
  4. Brute-force baseline that makes the monotonic stack optimization clear.

Time: O(n²)  |  Space: O(1) excluding output

Problem 7: Buildings With an Ocean View (Leetcode:1762)#

Problem Statement

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstruction. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Example 2:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

Constraints:

  • 1 <= n == heights.length <= 10^5
  • 1 <= heights[i] <= 10^9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findBuildings(self, heights: list[int]) -> list[int]:
        res = []
        max_right = 0

        for i in range(len(heights) - 1, -1, -1):
            if heights[i] > max_right:
                res.append(i)
                max_right = heights[i]

        return res[::-1]
Explanation:

  1. Scan from right to left, tracking the tallest building seen so far (max_right).
  2. A building has an ocean view iff its height exceeds everything to its right.
  3. Collect qualifying indices, then reverse to return ascending order.
  4. One pass, no explicit stack — but uses the same "pop shorter elements" intuition.

Time: O(n)  |  Space: O(n) for output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findBuildings(self, heights: list[int]) -> list[int]:
        stack = []  # indices with ocean view candidates

        for i in range(len(heights)):
            while stack and heights[stack[-1]] <= heights[i]:
                stack.pop()
            stack.append(i)

        return stack
Explanation:

  1. Scan left to right with a monotonic decreasing stack of candidate indices.
  2. When a taller building appears, pop all shorter buildings — they are blocked from the ocean.
  3. Remaining stack indices are exactly those with no taller building to their right.
  4. Stack order is already increasing, matching the required output format.

Time: O(n)  |  Space: O(n)

Problem 8: 132 Pattern (Leetcode:456)#

Problem Statement

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 105
  • -109 <= nums[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        stack = []  # candidate values for the middle (j) position
        second = float('-inf')  # best candidate for nums[k]

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < second:
                return True
            while stack and stack[-1] < nums[i]:
                second = stack.pop()
            stack.append(nums[i])

        return False
Explanation:

  1. Scan right to left; second holds the largest valid nums[k] seen so far (middle of a 132).
  2. Stack stores decreasing candidates for nums[j].
  3. When nums[i] is less than second, we found i < j < k with nums[i] < nums[k] < nums[j].
  4. Values popped from the stack become better second candidates because they sit to the right of a larger peak.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        n = len(nums)

        for j in range(1, n - 1):
            min_left = min(nums[:j])
            for k in range(j + 1, n):
                if min_left < nums[k] < nums[j]:
                    return True

        return False
Explanation:

  1. Fix the middle index j and enumerate every k > j.
  2. The smallest value left of j is the best candidate for nums[i].
  3. Check whether any nums[k] satisfies nums[i] < nums[k] < nums[j].
  4. Brute-force triple search; correct but quadratic time.

Time: O(n²)  |  Space: O(1)

Problem 9: Asteroid Collision (Leetcode:735)#

Problem Statement

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

  • 2 <= asteroids.length <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []

        for a in asteroids:
            while stack and stack[-1] > 0 and a < 0:
                if stack[-1] < -a:
                    stack.pop()
                    continue
                elif stack[-1] == -a:
                    stack.pop()
                a = 0
                break
            if a:
                stack.append(a)

        return stack
Explanation:

  1. Process asteroids left to right; the stack holds survivors so far.
  2. Collisions only happen when a right-moving asteroid meets a left-moving one (+ then -).
  3. Compare sizes: smaller explodes; equal sizes destroy both; larger right-mover keeps colliding.
  4. If the current asteroid survives all collisions, push it onto the stack.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        def collide(stack: list[int], left: int) -> list[int]:
            if not stack or left > 0 or stack[-1] < 0:
                return stack + [left]
            if stack[-1] < -left:
                return collide(stack[:-1], left)
            if stack[-1] == -left:
                return stack[:-1]
            return stack

        res = []
        for a in asteroids:
            res = collide(res, a)
        return res
Explanation:

  1. Recursive helper resolves one incoming asteroid against the current survivors.
  2. Same collision rules: only +/- pairs interact; smaller or equal explodes.
  3. If the left-moving asteroid wins, recursively check against the next stack top.
  4. Equivalent logic to the iterative stack, expressed recursively.

Time: O(n)  |  Space: O(n) recursion depth

Problem 10: Min Stack (Leetcode:155)#

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Constraints:

  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]
Explanation:

  1. Maintain two stacks: one for all values, one mirroring the current minimum.
  2. Push to min_stack only when the new value is <= the current minimum (handles duplicates).
  3. On pop, also pop from min_stack if the removed value equals the current min.
  4. getMin reads the top of min_stack in O(1).

Time: O(1) per operation  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class MinStack:
    def __init__(self):
        self.stack = []  # stores (value, min_so_far) pairs

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            self.stack.append((val, min(val, self.stack[-1][1])))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]
Explanation:

  1. Store each entry as a (value, min_so_far) tuple on a single stack.
  2. On push, min_so_far is the smaller of the new value and the previous minimum.
  3. Pop and top operate on the combined tuple — no second stack needed.
  4. Trades slightly more memory per entry for simpler bookkeeping.

Time: O(1) per operation  |  Space: O(n)

Problem 11: Basic Calculator (Leetcode:224)#

Problem Statement

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        res = 0
        num = 0
        sign = 1

        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == '+':
                res += sign * num
                num = 0
                sign = 1
            elif ch == '-':
                res += sign * num
                num = 0
                sign = -1
            elif ch == '(':
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif ch == ')':
                res += sign * num
                num = 0
                res *= stack.pop()  # sign before parenthesis
                res += stack.pop()  # result before parenthesis

        return res + sign * num
Explanation:

  1. Track running result, current number, and current sign (+1 or -1).
  2. On (, push the accumulated result and sign onto the stack, then reset for the subexpression.
  3. On ), finalize the subexpression, multiply by the saved sign, and add to the saved result.
  4. Stack handles nested parentheses by saving outer context at each open paren.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def calculate(self, s: str) -> int:
        def helper(i: int) -> tuple[int, int]:
            res = 0
            sign = 1
            num = 0

            while i < len(s):
                ch = s[i]
                if ch.isdigit():
                    num = num * 10 + int(ch)
                elif ch == '+':
                    res += sign * num
                    num, sign = 0, 1
                elif ch == '-':
                    res += sign * num
                    num, sign = 0, -1
                elif ch == '(':
                    num, i = helper(i + 1)
                elif ch == ')':
                    res += sign * num
                    return res, i
                i += 1

            return res + sign * num, i

        return helper(0)[0]
Explanation:

  1. Recursive helper evaluates a subexpression starting at index i.
  2. On (, recurse into the nested expression and use its result as the current number.
  3. On ), return the subexpression result and the closing index to the caller.
  4. Same semantics as the stack approach; recursion replaces explicit context saving.

Time: O(n)  |  Space: O(n) recursion depth

Problem 12: Trapping Rain Water (Leetcode:42)#

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:


Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def trap(self, height: list[int]) -> int:
        stack = []  # indices, monotonic decreasing by height
        water = 0

        for i, h in enumerate(height):
            while stack and height[stack[-1]] < h:
                bottom = stack.pop()
                if not stack:
                    break
                width = i - stack[-1] - 1
                bounded = min(height[stack[-1]], h) - height[bottom]
                water += width * bounded
            stack.append(i)

        return water
Explanation:

  1. Monotonic decreasing stack stores indices of bars forming a "basin wall."
  2. When a taller bar appears, the popped bar is the bottom of a trapped pool.
  3. Water height = min(left_wall, right_wall) - bottom; width spans between wall indices.
  4. Each index is pushed and popped once — classic monotonic stack for area accumulation.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        water = 0
        for i in range(n):
            water += min(left_max[i], right_max[i]) - height[i]

        return water
Explanation:

  1. Precompute the tallest bar to the left and right of every index.
  2. Water at index i = min(left_max[i], right_max[i]) - height[i].
  3. No stack needed — two prefix/suffix passes plus one accumulation pass.
  4. Alternative O(n) approach; useful when monotonic stack logic is harder to visualize.

Time: O(n)  |  Space: O(n)

Problem 13: Largest Rectangle in Histogram (Leetcode:84)#

Problem Statement

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

Example 1:


Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:


Input: heights = [2,4]
Output: 4

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []  # indices, monotonic increasing by height
        max_area = 0

        for i, h in enumerate(heights + [0]):
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        return max_area
Explanation:

  1. Append a sentinel 0 to force all remaining bars to be processed.
  2. Monotonic increasing stack tracks indices of bars that can extend rightward.
  3. When a shorter bar appears, pop and compute area using the popped height and span to the new top.
  4. Width extends from the new stack top (exclusive) to the current index (exclusive).

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        max_area = 0

        for i in range(n):
            min_height = heights[i]
            for j in range(i, n):
                min_height = min(min_height, heights[j])
                max_area = max(max_area, min_height * (j - i + 1))

        return max_area
Explanation:

  1. Fix a left boundary i and expand rightward to every j >= i.
  2. Track the minimum height in the range [i, j] — that is the rectangle height.
  3. Width is j - i + 1; update the global maximum area.
  4. Brute-force baseline highlighting why the monotonic stack achieves O(n).

Time: O(n²)  |  Space: O(1)

Problem 14: Number of Visible People in a Queue(Leetcode:1944)#

Problem Statement

There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.

Example 1:


Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.

Example 2:

Input: heights = [5,1,2,3,10]
Output: [4,1,1,1,0]

Constraints:

  • n == heights.length
  • 1 <= n <= 105
  • 1 <= heights[i] <= 105
  • All the values of heights are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def canSeePersonsCount(self, heights: list[int]) -> list[int]:
        n = len(heights)
        res = [0] * n
        stack = []  # indices, monotonic decreasing by height

        for i in range(n - 1, -1, -1):
            while stack and heights[stack[-1]] < heights[i]:
                res[i] += 1
                stack.pop()
            if stack:
                res[i] += 1
            stack.append(i)

        return res
Explanation:

  1. Scan right to left; stack holds people to the right that person i might see.
  2. Pop everyone shorter than person i — each popped person is directly visible.
  3. If anyone remains on the stack, person i can see exactly one taller person (then view is blocked).
  4. Monotonic decreasing stack counts visible people in O(n).

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def canSeePersonsCount(self, heights: list[int]) -> list[int]:
        n = len(heights)
        res = [0] * n

        for i in range(n):
            max_between = 0
            for j in range(i + 1, n):
                if min(heights[i], heights[j]) > max_between:
                    res[i] += 1
                max_between = max(max_between, heights[j])

        return res
Explanation:

  1. For each person i, scan every person j to their right.
  2. Track the maximum height strictly between i and j.
  3. Increment count when both endpoints are taller than everyone in between.
  4. Direct simulation of the problem definition; O(n²) but easy to verify correctness.

Time: O(n²)  |  Space: O(1) excluding output