Min Stack

Min Stack#

Twitter Handle LinkedIn Profile GitHub Profile LeetCode Problem Difficulty

from typing import List, Any

import math

class MinStack:

    def __init__(self):
        self._stack_items = []
        self._min = math.inf

    def push(self, val: int) -> None:
        curr_val = val
        if not self._stack_items:
            self._stack_items.append([curr_val, curr_val])
            return

        current_min = self._stack_items[-1][-1] # last ele is min

        if curr_val < current_min:
            curr_min_list = [curr_val, curr_val] # [curr, min]

        else:
            curr_min_list = [curr_val, current_min] # [curr, min]
        # else -> if no new min


        self._stack_items.append(curr_min_list)



    def pop(self) -> None:
        return self._stack_items.pop()


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


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

minStack = MinStack()

minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin() # return -3

-3

minStack.pop()

[-3, -3]

minStack.top()    # return 0

0

minStack.getMin() # return -2

-2

Reverse String using Stack#

Write a function rev_string(my_str) that uses a stack to reverse the characters in a string.

Time Complexity#

Assume the string has length \(n\).

Operations such as push, pop, is_empty() and != here are all \(\O(1)\).

Table 57 Time Complexity#

Operations

Time Complexity

push

\(\O(1)\)

pop

\(\O(1)\)

And since we traverse the given string one character at a time for at most \(n\) times, then the time complexity is \(\O(1) \times n \approx \O(n)\).

Space Complexity#

Assume the string has length \(n\).

The space complexity is at most \(\O(n)\) as we are just maintaining a stack with at most \(n\) elements pushed in.

Further Readings#