[Google Interview Question] The Minimum Stack Problem

[toc]

Company tags: Amazon, Apple, Microsoft, Oracle, Bloomberg

Problem Statement

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

  • MinStack() initializes the stack object.
  • push(val) pushes the element val onto the stack.
  • pop() removes the element on the top of the stack.
  • top() gets the top element of the stack.
  • getMin() retrieves the minimum element in the stack.

Constraints:

  1. -231 <= val <= 231 - 1
  2. Methods pop, top and getMin operations will always be called on non-empty stacks.
  3. At most 3 * 104 calls will be made to push, pop, top, and getMin.

Examples

Let’s have a look at some examples to improve our understanding of this problem.


Example 1:
Input: [“push”, “push”, “push”, “getMin”, “pop”, “top”, “getMin”]
[[-2], [0], [-3], [], [], [], [] ]
Output
[none, none, none, -3, none, 0, -2]
Explanation:
m = MinStack()
print(m.push(-2))
print(m.push(0))
print(m.push(-3))
print(m.getMin())
print(m.pop())
print(m.top())
print(m.getMin())

Example 2:
Input:
[“push”, “push”, “top”, “getMin”, “pop”, “push”, “getMin”]
[[2], [4], [], [], [], [-1], [] ]
Output
[none, none, 4, 2, none, none, -1]
Explanation:
m = MinStack()
print(m.push(2))
print(m.push(4))
print(m.top())
print(m.getMin())
print(m.pop())
print(m.push(-1))
print(m.getMin())

The Stack Data Structure

source: Wikipedia

Note: Python doesn’t have a built-in stack data structure because it’s not needed. You can simply create an empty list and call it stack. Then, you use the stack.append(x) method to push element x to the stack. And you sue the stack.pop() method to push the topmost element from the stack.

However, you must be well versed with the working principle of a stack to proceed with the solution. Here’s a quick overview:

A stack is a data structure used to store the items in LIFO (last-in-first-out) manner. The various operations that you can perform on the stack are:

  • Push – Adding an element on the stack refers to the push operation.
  • Pop – Removing an element from the stack is called pop operation.

Now that you know how the stack works, let’s dive into the methods to solve the given problem.

Method 1: Using Extra Space (Another Stack/List)

Approach: This is the simplest approach you can come up with during your interview. However this approach uses an extra space. The basic idea of this method is to use an extra stack that will store the minimum element of the original stack.

Let’s have a quick look at the algorithm and then let’s dive into the code.

Algorithm:

  1. Initialize two empty stacks in the init function.
  2. In the push function, push the value directly to the stack.
  3. If the min_stack is empty, or if the value of the current element is less than the value at the top of the min_stack, append the value at the top of the min_stack.
  4. In the pop function, check whether the value of the top element of the stack is equal to the top element of min_stack. If yes, pop the min_stack element and the stack element. Else, only pop the stack element.
  5. In the getMin and the top functions, return the value at the top of the stack.

Solution:

class MinStack:
    
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self,  x:int):
        self.stack.append(x)
        if not self.min_stack or x &lt;= self.min_stack[-1]:
            self.min_stack.append(x)
    
    def pop(self):
        if self.min_stack[-1] == self.stack[-1]:
            self.min_stack.pop()
        self.stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def getMin(self):
        return self.min_stack[-1]

Test Case Analysis:

# Example 1
m = MinStack()
print(m.push(-2))
print(m.push(0))
print(m.push(-3))
print(m.getMin())
print(m.pop())
print(m.top())
print(m.getMin())
# None None None -3 None 0 -2

# Example 2
m = MinStack()
print(m.push(2))
print(m.push(4))
print(m.top())
print(m.getMin())
print(m.pop())
print(m.push(-1))
print(m.getMin())
# None None 4 2 None None -1

Yeah! It passed all the test cases.

Complexity Analysis:

  • Time Complexity: This method takes constant time. Hence it has a runtime complexity of O(1)
  • Space Complexity: Extra O(n) space is required to create another stack.

Method 2: Without Using Extra Space

Approach: In the previous approach you had to use an extra space which accounted to the O(n) space complexty. However, this approach will allow you to save the extra space. In this approach, you have to use a variable that stores the minimum element.

Algorithm:

  1. Initialize a variable to store the current minimum value of the stack.
  2. In the push function, check whether the current value is less than the minimum value. If not, directly append the element to the stack.
  3. Else, update the minimum value. Also, append the value (2* x - current minimum element) into the stack. It will help you to get the minimum element while popping the element.
  4. In the pop function, check whether the value of the popped element is less than the minimum element. If yes, update the minimum value as (2* current minimum element - popping element)
  5. In the top function, if the value of the top element is less than the minimum element, return the minimum element. Else, return the top element.
  6. Note: Return the element stored in the variable that stores the minimum value directly when the getMin function gets called.

Solution:

class MinStack(object):
    def __init__(self):
        self.s = []
        self.m = None
    def push(self, x):
        if not self.s:
            self.s.append(x)
            self.m = x
            return 
        if x &lt; self.m:
            self.s.append(2*x-self.m)
            self.m = x
            return
        self.s.append(x)
       
    def pop(self):
        y = self.s[-1]
        self.s.pop()
        if y &lt; self.m:
            self.m = 2*self.m -y
    def top(self):
        y = self.s[-1]
        if y &lt; self.m:
            return self.m
        return y
        
    def getMin(self):
        return self.m

Test Case Analysis:

# Example 1
m = MinStack()
print(m.push(-2))
print(m.push(0))
print(m.push(-3))
print(m.getMin())
print(m.pop())
print(m.top())
print(m.getMin())
# None None None -3 None 0 -2

# Example 2
m = MinStack()
print(m.push(2))
print(m.push(4))
print(m.top())
print(m.getMin())
print(m.pop())
print(m.push(-1))
print(m.getMin())
# None None 4 2 None None -1

Yeah! It passed all the test cases.

Complexity Analysis:

  • Time Complexity: This method takes constant time. Hence the runtime complexity is O(1)
  • Space Complexity: No extra space is required. Thus, the space complexity for this approach is O(1).

Bonus Solution: Using The Same Stack

Approach: In this approach, you don’t have to use any extra variable or stack to store the minimum element. Rather, you will use the same stack to perform all the operations.

Algorithm:

  1. Initialize an empty stack.
  2. In the push function, first, find the minimum value between the current element and the existing minimum element. Push this minimum value into the stack. 
  3. Also, push the current value. This way, the minimum value exists in the position stack[-2] and the top value exists in the position stack[-1].
  4. Return this position values when getMin and top function gets called.
  5. While popping the element, call the pop function two times in order to pop both the top and the minimum value element.

Solution:

class MinStack(object):
    
   def __init__(self):
      self.stack = []
   def push(self, x):
      if self.stack:
         self.stack.append(min(self.stack[-2], x))
      else:
         self.stack.append(x)
      self.stack.append(x)
        
   def pop(self):
      if self.stack:
         self.stack.pop()
         self.stack.pop()
   def top(self):
      if self.stack:
         return self.stack[-1]
   def getMin(self):
      if self.stack:
         return self.stack[-2]

Test Case Analysis:

# Example 1
m = MinStack()
print(m.push(-2))
print(m.push(0))
print(m.push(-3))
print(m.getMin())
print(m.pop())
print(m.top())
print(m.getMin())
# None None None -3 None 0 -2

# Example 2
m = MinStack()
print(m.push(2))
print(m.push(4))
print(m.top())
print(m.getMin())
print(m.pop())
print(m.push(-1))
print(m.getMin())
# None None 4 2 None None -1

Yeah! It passed all the test cases.

Complexity Analysis:

  • Time Complexity: O(1) 
  • Space Complexity: No extra space is required. Hence the space complexity is also O(1).

Conclusion

Please stay tuned and subscribe for more interestin. I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

 Post Credits: Shubham Sayon and Rashi Agarwal


Recommended: Finxter Computer Science Academy

  • One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
  • So, do you want to master the art of web scraping using Python’s BeautifulSoup?
  • If the answer is yes – this course will take you from beginner to expert in Web Scraping.