educative.io

Min( ) Function Using a Stack pop() not correct

Courses
, ,
#1

I think pop() function solution is not correct;
We should always keep sorted stack on min_stack.
Please check my solution;

class MinStack:
# Constructor
def init(self):
self.main_stack = MyStack()
self.min_stack = MyStack()

def pop(self):
    result = self.main_stack.pop()
    tmp_list = []
    while not self.min_stack.is_empty() and self.min_stack.peek() != result:
        tmp_list.append(self.min_stack.pop())
    min_val = self.min_stack.pop()
    while len(tmp_list) > 0:
        self.min_stack.push(tmp_list.pop())
    return result

# Pushes value into new stack
def push(self, value):
    if self.min_stack.is_empty():
        self.min_stack.push(value)
    else:
        top = self.min_stack.peek()
        if value < top:
            self.min_stack.push(value)
        else:
            tmp_list = []
            while not self.min_stack.is_empty() and self.min_stack.peek() < value:
                tmp_list.append(self.min_stack.pop())
            self.min_stack.push(value)
            while len(tmp_list) > 0:
                self.min_stack.push(tmp_list.pop())
                
    self.main_stack.push(value)
    return True

# Returns minimum value from new stack in constant time
def min(self):
    return self.min_stack.peek()
#3

Hi,

The implementation of the push function given in the solution review pushes the value If the stack is empty. If not empty, it checks if the value is smaller than the top value of min_stack. If true, it pushes the value in min_stack. Otherwise, the top of the min_stack gets pushed again into the min_stack, which makes the min_stack and main_stack same in size. Where min_stack will always contain a min value at the top of the stack.

Each time a value is popped from the main_stack, the value is popped from the min_stack too, which makes the implementation optimum and correct.

I hope you have understood the solution now.

Thank you!