# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What Went Well**

I knew that this problem required two stacks., one to act as the regular stack and then a min stack to abide by the O(1) operation time for each method.

**How I Can Improve**

I can take advice from the most optimal solution and learn when to add more conditions to reduce the execution time for non-critical values.

**Comments**

The solution statistics for my code and the optimal solution varied by over 50%, so as usually take them with a grain of salt.

# Data Structure Description

**Stack -** A stack is similar to an array, except you are only allowed to push/pop (add/remove) from the end of the stack. A stack follows the first in, last out, or FILO theme.

Since Python already has O(1) push (append) and pop (pop) operations, we do not need to use any libraries.

**Visual Examples** Visual of a stack being mutated, click to view

# Solution Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(1) - All the operations are O(1), although there are multiple O(1) instructions. Regardless, big O ignores constants, resulting in the O(n) time complexity.

**Space Complexity**

O(n) - In reality, we store each input value twice, resulting in O(2 * n), but big O ignores constant multiples of n. So, the end result is a space complexity of O(n).

**Runtime Beats**

65.57% of other submissions

**Memory Beats**

49.72% of other sumbissions

# Solution

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 MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, value: int) -> None:
self.stack.append(val)
# Assign the smallest value to val out of the
# current last element and the input value
if self.minStack:
val = min(val,self.minStack[-1])
self.minStack.append(val)
def pop(self) -> None:
# Since stacks follow the FILO principle, we are unable
# to remove the minimum from the stack without also removing
# all of its occurrences from the minStack, therefore we do not
# need to perform extra operations when poping from minStack
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]