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]