Min Max Stack Construction
The objective of this solution is to implement a stack data structure called a MinMaxStack, which is a stack that allows constant-time retrieval of both the minimum and maximum elements currently in the stack.
class MinMaxStack:
def __init__(self):
self.minMaxStack =[]
self.stack =[]
def peek(self):
return self.stack[len(self.stack)-1]
def pop(self):
self.minMaxStack.pop()
return self.stack.pop()
def push(self, number):
newMinMax ={"min": number, "max": number}
if len(self.minMaxStack):
lastMinMax= self.minMaxStack[len(self.minMaxStack)-1]
newMinMax["min"] =min(lastMinMax["min"], number)
newMinMax["max"] =max(lastMinMax["max"], number)
self.minMaxStack.append(newMinMax)
self.stack.append(number)
def getMin(self):
return self.minMaxStack[len(self.minMaxStack) -1]["min"]
def getMax(self):
return self.minMaxStack[len(self.minMaxStack) -1]["max"]
min_max = MinMaxStack()
min_max.push(5)
print(f"round 1::: min : {min_max.getMin()}, max : {min_max.getMax()}, peek : {min_max.peek()}")
min_max.push(7)
print(f"round 2::: min : {min_max.getMin()}, max : {min_max.getMax()}, peek : {min_max.peek()}")
min_max.push(2)
The solution to the Problem
The MinMaxStack aims to solve the problem of efficiently retrieving the minimum and maximum elements from a stack, along with the standard stack operations (push, pop, peek).
Solution Overview
The MinMaxStack is implemented using two stacks: one stack (self.stack) to store the actual elements and another stack (self.minMaxStack) to store tuples containing the minimum and maximum elements seen so far in the stack.
Initialization (__init__)
Initializes two empty lists, self.minMaxStack, and self.stack, to store the minimum and maximum elements and the actual elements, respectively.
Push Operation (push)
Adds a new element to the stack. When pushing a new element, it also updates the self.minMaxStack with the current minimum and maximum elements seen so far.
This is achieved by comparing the new element with the previous minimum and maximum elements stored in the self.minMaxStack.
Pop Operation (pop)
Removes and returns the top element from the stack. It also removes the corresponding tuple from the self.minMaxStack, as the element is no longer present in the stack.
Peek Operation (peek)
Returns the top element of the stack without removing it.
Get Minimum (getMin) and Maximum (getMax) Operations
Returns the current minimum and maximum elements in the stack by accessing the top tuple from the self.minMaxStack.
Time Complexity
Push, Pop, Peek Operations
All stack operations (push, pop, and peek) have a time complexity of O(1) as they involve adding/removing/accessing elements from the end of the list, which can be done in constant time.
Get Minimum (getMin) and Maximum (getMax) Operations
Both operations also have a time complexity of O(1) as they directly access the top tuple from the self.minMaxStack.
Space Complexity
The space complexity of the MinMaxStack is O(n), where n is the number of elements in the stack. This is because it uses additional space to store the self.minMaxStack, which can grow linearly with the number of elements in the stack.
Applicability
This solution is useful in various scenarios, such as tracking the range of values in a sliding window or optimizing certain algorithms that require accessing the minimum and maximum elements in a stack.