Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Min Stack

Posted on January 10, 2018July 26, 2020 by braindenny

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.



Similar Problems:

  • Max Stack
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #oodesign, #designstack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/min-stack
## Basic Ideas: List with elements of (value, min_value)
##    -2 0 -3  4
##    linked list:
##     (-2, -2), (0, -2), (-3, -3), (4, -3)
##
##    length: element count
## Complexity:  Time: O(1), Space: O(n)
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.length = 0
        self.min_value = None
        self.values = []


    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if self.length == 0:
            element = (x, x)
            self.min_value = x
        else:
            if x > self.min_value:
                element = (x, self.min_value)
            else:
                self.min_value = x
                element = (x, x)
        self.values.append(element)
        self.length += 1

    def pop(self):
        """
        :rtype: void
        """
        if self.length == 0:
            return

        if self.length == 1:
            self.min_value = None
        else:
            (x, previous_min_value) = self.values[-2]
            self.min_value = previous_min_value

        self.values.pop()
        self.length -= 1

    def top(self):
        """
        :rtype: int
        """
        if len(self.values) == 0:
            return None
        else:
            (x, _min_value) = self.values[-1]
            return x

    def getMin(self):
        """
        :rtype: int
        """
        return self.min_value
linkedin
github
slack

Post Views: 1
Posted in MediumTagged #inspiring, designstack, oodesign

Post navigation

LeetCode: LRU Cache
LeetCode: Guess Number Higher or Lower II

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.