Daily Archives: October 24, 2021

C# || MinStack – How To Implement Minimum Element Stack Using C#

The following is a module with functions which demonstrates how to implement minimum element stack using C#.


1. MinStack – 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.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

Example 1:


Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2


2. MinStack – Solution

The following is a solution which demonstrates how to implement minimum element stack.

The main idea of this solution is to have a way to keep track of the minimum value every time an item is pushed onto the stack.

When a new value is pushed onto the stack, it is checked against the last minimum to see if the current value is a minimum. Every time a new item is added, we keep track of the minimum value for each push.

In this solution:

  • When the Top function is called, the current top value is returned
  • When the GetMin function is called, the minimum value at the time the top value was pushed onto the stack is returned
  • When the Push function is called, the value and the current minimum value is pushed onto the stack

A list< pair < int, int>> is used to keep track of the current item pushed onto the stack, and the minimum value at the time the item was pushed onto the stack.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


[null,null,null,null,-3,null,0,-2]