Design and Implement Special Stack Data Structure | Added Space Optimized Version

Last Updated : 20 Feb, 2023

Question: Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, . etc.

Example:

Consider the following SpecialStack
16  --> TOP
15
29
19
18

When getMin() is called it should 
return 15, which is the minimum 
element in the current stack. 

If we do pop two times on stack, 
the stack becomes
29  --> TOP
19
18

When getMin() is called, it should 
return 18 which is the minimum in 
the current stack.

Solution:

Use two stacks: one to store actual stack elements and the other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of the auxiliary stack is always the minimum. Let us see how push() and pop() operations work.

Push(int x) // inserts an element x to Special Stack

1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
1. If x is smaller than y then push x to the auxiliary stack.
2. If x is greater than y then push y to the auxiliary stack.

int Pop() // removes an element from Special Stack and return the removed element

pop the top element from the auxiliary stack.
pop the top element from the actual stack and return it. Step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

int getMin() // returns the minimum element from Special Stack

Return the top element of the auxiliary stack.

We can see that all the above operations are O(1).

Let us see an example. Let us assume that both stacks are initially empty and 18, 19, 29, 15, and 16 are inserted to the SpecialStack.

When we insert 18, both stacks change to following.
Actual Stack
18 <--- top     
Auxiliary Stack
18 <---- top

When 19 is inserted, both stacks change to following.
Actual Stack
19 <--- top     
18
Auxiliary Stack
18 <---- top
18

When 29 is inserted, both stacks change to following.
Actual Stack
29 <--- top     
19
18
Auxiliary Stack
18 <---- top
18
18

When 15 is inserted, both stacks change to following.
Actual Stack
15 <--- top     
29
19 
18
Auxiliary Stack
15 <---- top
18
18
18

When 16 is inserted, both stacks change to following.
Actual Stack
16 <--- top     
15
29
19 
18
Auxiliary Stack
15 <---- top
15
18
18
18

The following is the implementation for SpecialStack class. In the below implementation, SpecialStack inherits from Stack and has one Stack object min which works as an auxiliary stack.

C++

#include <iostream> 
#include <stdlib.h> 
  
using namespace std; 
  
/* A simple stack class with  
basic stack functionalities */
class Stack { 
private: 
    static const int max = 100; 
    int arr[max]; 
    int top; 
  
public: 
    Stack() { top = -1; } 
    bool isEmpty(); 
    bool isFull(); 
    int pop(); 
    void push(int x); 
}; 
  
/* Stack's member method to check  
if the stack is empty */
bool Stack::isEmpty() 
{ 
    if (top == -1) 
        return true; 
    return false; 
} 
  
/* Stack's member method to check  
if the stack is full */
bool Stack::isFull() 
{ 
    if (top == max - 1) 
        return true; 
    return false; 
} 
  
/* Stack's member method to remove  
an element from it */
int Stack::pop() 
{ 
    if (isEmpty()) { 
        cout << "Stack Underflow"; 
        abort(); 
    } 
    int x = arr[top]; 
    top--; 
    return x; 
} 
  
/* Stack's member method to insert  
an element to it */
void Stack::push(int x) 
{ 
    if (isFull()) { 
        cout << "Stack Overflow"; 
        abort(); 
    } 
    top++; 
    arr[top] = x; 
} 
  
/* A class that supports all the stack  
operations and one additional 
  operation getMin() that returns the  
minimum element from stack at 
  any time.  This class inherits from  
the stack class and uses an 
  auxiliary stack that holds minimum  
elements */
class SpecialStack : public Stack { 
    Stack min; 
  
public: 
    int pop(); 
    void push(int x); 
    int getMin(); 
}; 
  
/* SpecialStack's member method to insert 
 an element to it. This method 
   makes sure that the min stack is also  
updated with appropriate minimum 
   values */
void SpecialStack::push(int x) 
{ 
    if (isEmpty() == true) { 
        Stack::push(x); 
        min.push(x); 
    } 
    else { 
        Stack::push(x); 
        int y = min.pop(); 
        min.push(y); 
        if (x < y) 
            min.push(x); 
        else
            min.push(y); 
    } 
} 
  
/* SpecialStack's member method to  
remove an element from it. This method 
   removes top element from min stack also. */
int SpecialStack::pop() 
{ 
    int x = Stack::pop(); 
    min.pop(); 
    return x; 
} 
  
/* SpecialStack's member method to get 
 minimum element from it. */
int SpecialStack::getMin() 
{ 
    int x = min.pop(); 
    min.push(x); 
    return x; 
} 
  
/* Driver program to test SpecialStack 
 methods */
int main() 
{ 
    SpecialStack s; 
    s.push(10); 
    s.push(20); 
    s.push(30); 
    cout << s.getMin() << endl; 
    s.push(5); 
    cout << s.getMin(); 
    return 0; 
} 

Java

// Java implementation of SpecialStack 
// Note : here we use Stack class for 
// Stack implementation 
  
import java.util.Stack; 
  
/* A class that supports all the  
stack operations and one additional 
operation getMin() that returns  
the minimum element from stack at 
any time. This class inherits from  
the stack class and uses an 
auxiliary stack that holds minimum 
 elements */
  
class SpecialStack extends Stack<Integer> { 
    Stack<Integer> min = new Stack<>(); 
  
    /* SpecialStack's member method to  
insert an element to it. This method 
    makes sure that the min stack is  
also updated with appropriate minimum 
    values */
    void push(int x) 
    { 
        if (isEmpty() == true) { 
            super.push(x); 
            min.push(x); 
        } 
        else { 
            super.push(x); 
            int y = min.pop(); 
            min.push(y); 
            if (x < y) 
                min.push(x); 
            else
                min.push(y); 
        } 
    } 
  
    /* SpecialStack's member method to  
insert an element to it. This method 
    makes sure that the min stack is  
also updated with appropriate minimum 
    values */
    public Integer pop() 
    { 
        int x = super.pop(); 
        min.pop(); 
        return x; 
    } 
  
    /* SpecialStack's member method to get  
minimum element from it. */
    int getMin() 
    { 
        int x = min.pop(); 
        min.push(x); 
        return x; 
    } 
  
    /* Driver program to test SpecialStack  
methods */
    public static void main(String[] args) 
    { 
        SpecialStack s = new SpecialStack(); 
        s.push(10); 
        s.push(20); 
        s.push(30); 
        System.out.println(s.getMin()); 
        s.push(5); 
        System.out.println(s.getMin()); 
    } 
} 
// This code is contributed by Sumit Ghosh 

Python3

# Python3 program for the 
# above approach 
# A simple stack class with   
# basic stack functionalities 
class stack: 
  
  def __init__(self): 
  
    self.array = [] 
    self.top = -1
    self.max = 100  
  
  # Stack's member method to check  
  # if the stack is empty 
  def isEmpty(self): 
  
    if self.top == -1: 
      return True
    else: 
      return False  
  
  # Stack's member method to check 
  # if the stack is full   
  def isFull(self):   
      
    if self.top == self.max - 1: 
      return True
    else: 
      return False   
  
  # Stack's member method to  
  # insert an element to it    
  
  def push(self, data): 
  
    if self.isFull(): 
      print('Stack OverFlow') 
      return
    else: 
      self.top += 1
      self.array.append(data)      
  
  # Stack's member method to  
  # remove an element from it  
  def pop(self): 
  
    if self.isEmpty(): 
      print('Stack UnderFlow') 
      return
    else:  
      self.top -= 1
      return self.array.pop() 
  
# A class that supports all the stack   
# operations and one additional  
# operation getMin() that returns the  
# minimum element from stack at  
# any time.  This class inherits from 
# the stack class and uses an  
# auxiliary stack that holds  
# minimum elements   
class SpecialStack(stack): 
  
  def __init__(self): 
    super().__init__() 
    self.Min = stack()   
  
  # SpecialStack's member method to  
  # insert an element to it. This method  
  # makes sure that the min stack is also 
  # updated with appropriate minimum 
  # values  
  def push(self, x): 
  
    if self.isEmpty(): 
      super().push(x) 
      self.Min.push(x) 
    else: 
      super().push(x) 
      y = self.Min.pop() 
      self.Min.push(y) 
      if x <= y: 
        self.Min.push(x) 
      else: 
        self.Min.push(y)   
  
  # SpecialStack's member method to   
  # remove an element from it. This  
  # method removes top element from  
  # min stack also.  
  def pop(self): 
  
    x = super().pop() 
    self.Min.pop() 
    return x   
  
  # SpecialStack's member method  
  # to get minimum element from it. 
  def getmin(self): 
  
    x = self.Min.pop() 
    self.Min.push(x) 
    return x 
  
# Driver code 
if __name__ == '__main__': 
    
  s = SpecialStack() 
  s.push(10) 
  s.push(20) 
  s.push(30) 
  print(s.getmin()) 
  s.push(5) 
  print(s.getmin()) 
  
# This code is contributed by rachitkatiyar99

C#

using System; 
using System.Collections.Generic; 
  
// A class that supports all the stack operations 
// and one additional operation `GetMin` 
// that returns the minimum element from the stack at any time.  
// This class inherits from the `Stack` class and uses an  
// auxiliary stack to hold minimum elements. 
class SpecialStack : Stack<int> 
{ 
    // Auxiliary stack to store minimum elements. 
    Stack<int> min = new Stack<int>(); 
  
    // Method to insert an element to the stack. 
    // Makes sure that the min stack is also updated  
    // with appropriate minimum values. 
    public void Push(int x) 
    { 
        if (Count == 0) 
        { 
            // If the stack is empty, simply add the 
            // element and push it to the `min` stack. 
            base.Push(x); 
            min.Push(x); 
        } 
        else
        { 
            // Add the element to the stack. 
            base.Push(x); 
            int y = min.Pop(); 
            min.Push(y); 
  
            // If the current element is less than the current minimum,  
            // add it to the `min` stack. 
            if (x < y) 
                min.Push(x); 
            else
                min.Push(y); 
        } 
    } 
  
    // Method to remove an element from the stack. 
    // Makes sure that the min stack is also updated with  
    // appropriate minimum values. 
    public new int Pop() 
    { 
        // Pop the element from the stack. 
        int x = base.Pop(); 
  
        // Pop the minimum value from the `min` stack. 
        min.Pop(); 
  
        return x; 
    } 
  
    // Method to get the minimum element from the stack. 
    public int GetMin() 
    { 
        int x = min.Pop(); 
        min.Push(x); 
        return x; 
    } 
  
    static void Main(string[] args) 
    { 
        SpecialStack s = new SpecialStack(); 
        s.Push(10); 
        s.Push(20); 
        s.Push(30); 
        Console.WriteLine(s.GetMin()); 
        s.Push(5); 
        Console.WriteLine(s.GetMin()); 
        Console.ReadLine(); 
    } 
} 

Javascript

class stack { 
  constructor() { 
    this.array = []; 
    this.top = -1; 
    this.max = 100; 
  } 
  
  isEmpty() { 
    if (this.top == -1) { 
      return true; 
    } else { 
      return false; 
    } 
  } 
  
  isFull() { 
    if (this.top == this.max - 1) { 
      return true; 
    } else { 
      return false; 
    } 
  } 
  
  push(data) { 
    if (this.isFull()) { 
      console.log("Stack OverFlow"); 
      return; 
    } else { 
      this.top += 1; 
      this.array.push(data); 
    } 
  } 
  
  pop() { 
    if (this.isEmpty()) { 
      console.log("Stack UnderFlow"); 
      return; 
    } else { 
      this.top -= 1; 
      return this.array.pop(); 
    } 
  } 
} 
  
class SpecialStack extends stack { 
  constructor() { 
    super(); 
    this.Min = new stack(); 
  } 
  
  push(x) { 
    if (this.isEmpty()) { 
      super.push(x); 
      this.Min.push(x); 
    } else { 
      super.push(x); 
      let y = this.Min.pop(); 
      this.Min.push(y); 
      if (x <= y) { 
        this.Min.push(x); 
      } else { 
        this.Min.push(y); 
      } 
    } 
  } 
  
  pop() { 
    let x = super.pop(); 
    this.Min.pop(); 
    return x; 
  } 
  
  getmin() { 
    let x = this.Min.pop(); 
    this.Min.push(x); 
    return x; 
  } 
} 
  
let s = new SpecialStack(); 
s.push(10); 
s.push(20); 
s.push(30); 
console.log(s.getmin()); 
s.push(5); 
console.log(s.getmin()); 

Output

10
5

Complexity Analysis:

Time Complexity:
1. For insert operation: O(1) (As insertion ‘push’ in a stack takes constant time)
2. For delete operation: O(1) (As deletion ‘pop’ in a stack takes constant time)
3. For ‘Get Min’ operation: O(1) (As we have used an auxiliary stack which has it’s top as the minimum element)
Auxiliary Space: O(n).
Use of auxiliary stack for storing values.

Space Optimized Version

The above approach can be optimized. We can limit the number of elements in the auxiliary stack. We can push only when the incoming element of the main stack is smaller than or equal to the top of the auxiliary stack. Similarly during pop, if the pop-off element equal to the top of the auxiliary stack, remove the top element of the auxiliary stack. Following is the modified implementation of push() and pop().

C++

/* SpecialStack's member method to  
   insert an element to it. This method 
   makes sure that the min stack is  
   also updated with appropriate minimum 
   values */
void SpecialStack::push(int x) 
{ 
    if (isEmpty() == true) { 
        Stack::push(x); 
        min.push(x); 
    } 
    else { 
        Stack::push(x); 
        int y = min.pop(); 
        min.push(y); 
  
        /* push only when the incoming element 
           of main stack is smaller  
        than or equal to top of auxiliary stack */
        if (x <= y) 
            min.push(x); 
    } 
} 
  
/* SpecialStack's member method to  
   remove an element from it. This method 
   removes top element from min stack also. */
int SpecialStack::pop() 
{ 
    int x = Stack::pop(); 
    int y = min.pop(); 
  
    /* Push the popped element y back  
       only if it is not equal to x */
    if (y != x) 
        min.push(y); 
  
    return x; 
} 

Java

/* SpecialStack's member method to  
insert an element to it. This method 
makes sure that the min stack is  
also updated with appropriate minimum 
values */
  
void push(int x) 
{ 
    if (isEmpty() == true) { 
        super.push(x); 
        min.push(x); 
    } 
    else { 
        super.push(x); 
        int y = min.pop(); 
        min.push(y); 
  
        /* push only when the incoming  
           element of main stack is smaller  
        than or equal to top of auxiliary stack */
        if (x <= y) 
            min.push(x); 
    } 
} 
  
/* SpecialStack's member method to  
   remove an element from it. This method 
   removes top element from min stack also. */
public Integer pop() 
{ 
    int x = super.pop(); 
    int y = min.pop(); 
  
    /* Push the popped element y back  
       only if it is not equal to x */
    if (y != x) 
        min.push(y); 
    return x; 
} 
  
// This code is contributed by Sumit Ghosh 

Python3

''' SpecialStack's member method to  
insert an element to it. This method 
makes sure that the min stack is  
also updated with appropriate minimum 
values '''
  
def push(x): 
    if (isEmpty() == True): 
        super.append(x); 
        min.append(x); 
      
    else: 
        super.append(x); 
        y = min.pop(); 
        min.append(y); 
  
        ''' push only when the incoming  
           element of main stack is smaller  
        than or equal to top of auxiliary stack '''
        if (x <= y): 
            min.append(x); 
      
  
  
''' SpecialStack's member method to  
   remove an element from it. This method 
   removes top element from min stack also. '''
def pop(): 
    x = super.pop(); 
    y = min.pop(); 
  
    ''' Push the popped element y back  
       only if it is not equal to x '''
    if (y != x): 
        min.append(y); 
    return x; 
  
  
# This code contributed by umadevi9616  

C#

/* SpecialStack's member method to  
insert an element to it. This method 
makes sure that the min stack is  
also updated with appropriate minimum 
values */
  
void push(int x) 
{ 
    if (min.Count==0) { 
        super.Push(x); 
        min.Push(x); 
    } 
    else { 
        super.Push(x); 
        int y = min.Pop(); 
        min.Push(y); 
  
        /* push only when the incoming  
           element of main stack is smaller  
        than or equal to top of auxiliary stack */
        if (x <= y) 
            min.Push(x); 
    } 
} 
  
/* SpecialStack's member method to  
   remove an element from it. This method 
   removes top element from min stack also. */
public int pop() 
{ 
    int x = super.Pop(); 
    int y = min.Pop(); 
  
    /* Push the popped element y back  
       only if it is not equal to x */
    if (y != x) 
        min.Push(y); 
    return x; 
} 
  
// This code is contributed by umadevi9616 

Javascript

<script> 
/* SpecialStack's member method to  
insert an element to it. This method 
makes sure that the min stack is  
also updated with appropriate minimum 
values */
  
function push(x) 
{ 
    if (isEmpty() == true) { 
        super.push(x); 
        min.push(x); 
    } 
    else { 
        super.push(x); 
        var y = min.pop(); 
        min.push(y); 
  
        /* push only when the incoming  
           element of main stack is smaller  
        than or equal to top of auxiliary stack */
        if (x <= y) 
            min.push(x); 
    } 
} 
  
/* SpecialStack's member method to  
   remove an element from it. This method 
   removes top element from min stack also. */
 function pop() 
{ 
    var x = super.pop(); 
    var y = min.pop(); 
  
    /* Push the popped element y back  
       only if it is not equal to x */
    if (y != x) 
        min.push(y); 
    return x; 
} 
  
// This code is contributed by umadevi9616  
</script> 

Complexity Analysis:

Time Complexity:
1. For Insert operation: O(1) (As insertion ‘push’ in a stack takes constant time)
2. For Delete operation: O(1) (As deletion ‘pop’ in a stack takes constant time)
3. For ‘Get Min’ operation: O(1) (As we have used an auxiliary which has it’s top as the minimum element)
Auxiliary Space: O(n).
The complexity in the worst case is the same as above but in other cases, it will take slightly less space than the above approach as repetition is neglected.

Further optimized O(1) time complexity and O(1) space complexity solution :

The above approach can be optimized further and the solution can be made to work in O(1) time complexity and O(1) space complexity. The idea is to store min element found till current insertion) along with all the elements as a reminder of a DUMMY_VALUE, and the actual element as a multiple of the DUMMY_VALUE.
For example, while pushing an element ‘e’ into the stack, store it as (e * DUMMY_VALUE + minFoundSoFar), this way we know what was the minimum value present in the stack at the time ‘e’ was being inserted.

To pop the actual value just return e/DUMMY_VALUE and set the new minimum as (minFoundSoFar % DUMMY_VALUE).

Note: Following method will fail if we try to insert DUMMY_VALUE in the stack, so we have to make our selection of DUMMY_VALUE carefully.
Let’s say the following elements are being inserted in the stack – 3 2 6 1 8 5

d is dummy value.

s is wrapper stack

top is top element of the stack

min is the minimum value at that instant when the elements were inserted/removed

The following steps shows the current state of the above variables at any instant –

s.push(3);
min=3 //updated min as stack here is empty
s = {3*d + 3}
top = (3*d + 3)/d = 3

s.push(2);
min = 2 //updated min as min > current element
s = {3*d + 3-> 2*d + 2}
top = (2*d + 2)/d = 2

s.push(6);
min = 2
s = {3*d + 3-> 2*d + 2-> 6*d + 2}
top = (6*d + 2)/d = 6

s.push(1);
min = 1 //updated min as min > current element
s = {3*d + 3-> 2*d + 2-> 6*d + 2 -> 1*d + 1}
top = (1*d + 1)/d = 1

s.push(8);
min = 1
s = {3*d + 3-> 2*d + 2-> 6*d + 2 -> 1*d + 1 -> 8*d + 1}
top = (8*d + 1)/d = 8

s.push(5);
min = 1
s = {3*d + 3-> 2*d + 2-> 6*d + 2 -> 1*d + 1 -> 8*d + 1 -> 5*d + 1}
top = (5*d + 1)/d = 5

s.pop();
s = {3*d + 3 -> 2*d + 2 -> 6*d + 2 -> 1*d + 1 -> 8*d + 1 -> 5*d + 1}
top = (5*d + 1)/d = 5
min = (8*d + 1)%d = 1 // min is always remainder of the second top element in stack.

s.pop();
s = {3*d + 3 -> 2*d + 2-> 6*d + 2 -> 1*d + 1 -> 8*d + 1}
top = (8*d + 1)/d = 8
min = (1*d + 1)%d = 1

s.pop()
s = {3*d + 3 -> 2*d + 2-> 6*d + 2 -> 1*d + 1}
top = (1*d + 1)/d = 1
min = (6*d + 2)%d = 2

s.pop()
s = {3*d + 3-> 2*d + 2-> 6*d + 2}
top = (6*d + 2)/d = 6
min = (2*d + 2)%d = 2

s.pop()
s = {3*d + 3-> 2*d + 2}
top = (2*d + 2)/d = 2
min = (3*d + 3)%d = 3

s.pop()
s = {3*d + 3}
top = (3*d + 3)/d = 3
min = -1 // since stack is now empty

C++

#include <iostream> 
#include <stack> 
#include <vector> 
using namespace std; 
  
/* A special stack having peek() pop() and 
 * push() along with additional getMin() that 
 * returns minimum value in a stack without  
 * using extra space and all operations in O(1) 
 * time.. ???? */
class SpecialStack 
{ 
      
    // Sentinel value for min 
    int min = -1;   
      
    // DEMO_VALUE 
    static const int demoVal = 9999;  
    stack<int> st; 
  
public: 
  
    void getMin() 
    { 
        cout << "min is: " << min << endl; 
    } 
  
    void push(int val) 
    { 
          
        // If stack is empty OR current element  
        // is less than min, update min. 
        if (st.empty() || val < min) 
        { 
            min = val; 
        } 
          
        // Encode the current value with 
        // demoVal, combine with min and 
        // insert into stack 
        st.push(val * demoVal + min);  
        cout << "pushed: " << val << endl; 
    } 
  
    int pop() 
    {     
        // if stack is empty return -1; 
        if ( st.empty() ) { 
          cout << "stack underflow" << endl ; 
          return -1; 
        } 
        
        int val = st.top(); 
        st.pop(); 
          
        // If stack is empty, there would 
        // be no min value present, so 
        // make min as -1 
        if (!st.empty())  
            min = st.top() % demoVal; 
        else
            min = -1; 
              
        cout << "popped: " << val / demoVal << endl; 
          
        // Decode actual value from 
        // encoded value 
        return val / demoVal;  
    } 
  
    int peek() 
    { 
          
        // Decode actual value 
        // from encoded value 
        return st.top() / demoVal;  
    } 
}; 
  
// Driver Code 
int main() 
{ 
    SpecialStack s; 
  
    vector<int> arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 }; 
  
    for(int i = 0; i < arr.size(); i++) 
    { 
        s.push(arr[i]); 
        s.getMin(); 
    } 
      
    cout << endl; 
    for(int i = 0; i < arr.size(); i++) 
    { 
        s.pop(); 
        s.getMin(); 
    } 
    return 0; 
} 
  
// This code is contributed by scisaif

Java

import java.util.Stack; 
  
/* A special stack having peek() pop() and push() along with 
 * additional getMin() that returns minimum value in a stack 
 * without using extra space and all operations in O(1) 
 * time.. 🙂 
 * */
public class SpecialStack { 
  
    int min = -1; // sentinel value for min 
    static int demoVal = 9999; // DEMO_VALUE 
    Stack<Integer> st = new Stack<Integer>(); 
  
    void getMin() { System.out.println("min is: " + min); } 
  
    void push(int val) 
    { 
        // if stack is empty OR current element is less than 
        // min, update min.. 
        if (st.isEmpty() || val < min) { 
            min = val; 
        } 
  
        st.push(val * demoVal 
                + min); // encode the current value with 
                        // demoVal, combine with min and 
                        // insert into stack 
        System.out.println("pushed: " + val); 
    } 
  
    int pop() 
    {     
        // if stack is empty return -1; 
        if (st.isEmpty() ) { 
             System.out.println("stack underflow");  
               return -1; 
          } 
        
        int val = st.pop(); 
  
        if (!st.isEmpty()) // if stack is empty, there would 
                           // be no min value present, so 
                           // make min as -1 
            min = st.peek() % demoVal; 
        else
            min = -1; 
        System.out.println("popped: " + val / demoVal); 
        return val / demoVal; // decode actual value from 
                              // encoded value 
    } 
  
    int peek() 
    { 
        return st.peek() / demoVal; // decode actual value 
                                    // from encoded value 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        SpecialStack s = new SpecialStack(); 
  
        int[] arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 }; 
  
        for (int i = 0; i < arr.length; i++) { 
            s.push(arr[i]); 
            s.getMin(); 
        } 
        System.out.println(); 
        for (int i = 0; i < arr.length; i++) { 
            s.pop(); 
            s.getMin(); 
        } 
    } 
}

Python3

# A special stack having peek() pop() and 
# push() along with additional getMin() that 
# returns minimum value in a stack without 
# using extra space and all operations in O(1) 
# time.. ???? 
class SpecialStack: 
  
    def __init__(self): 
        # Sentinel value for min 
        self.minm = -1
  
        # DEMO_VALUE 
        SpecialStack.demoVal = 9999
        self.st = [] 
  
    def getMin(self): 
        print("min is: ", self.minm) 
  
    def push(self, val): 
  
        # If stack is empty OR current element 
        # is less than min, update min. 
        if len(self.st) == 0 or val < self.minm: 
            self.minm = val 
  
        # Encode the current value with 
        # demoVal, combine with min and 
        # insert into stack 
        self.st.append(val*self.demoVal + self.minm) 
        print("pushed: ", val) 
  
    def pop(self): 
  
        # if stack is empty return -1 
        if len(self.st) == 0: 
            print("stack underflow") 
            return -1
  
        val = self.st.pop() 
  
        # If stack is empty, there would 
        # be no min value present, so 
        # make min as -1 
        if len(self.st) != 0: 
            self.minm = self.st[-1] % self.demoVal 
        else: 
            self.minm = -1
  
        print("popped: ", val // self.demoVal) 
  
        # Decode actual value from 
        # encoded value 
        return val // self.demoVal 
  
    def peek(self): 
  
        # Decode actual value 
        # from encoded value 
        return self.st[-1] // self.demoVal 
  
# Driver Code 
if __name__ == "__main__": 
    s = SpecialStack() 
  
    arr = [3, 2, 6, 1, 8, 5, 5, 5, 5] 
  
    for i in range(len(arr)): 
        s.push(arr[i]) 
        s.getMin() 
  
    print("\n") 
    for i in range(len(arr)): 
        s.pop() 
        s.getMin() 
  
        # This code is contributed by pankajkumar70792.

C#

using System; 
using System.Collections.Generic; 
  
  
/* A special stack having peek() pop() and push() along with 
 * additional getMin() that returns minimum value in a stack 
 * without using extra space and all operations in O(1) 
 * time.. 🙂 
 * */
public class SpecialStack { 
  
    int min = -1; // sentinel value for min 
    static int demoVal = 9999; // DEMO_VALUE 
    Stack<int> st = new Stack<int>(); 
  
    void getMin() { Console.WriteLine("min is: " + min); } 
  
    void push(int val) 
    { 
        // if stack is empty OR current element is less than 
        // min, update min.. 
        if (st.Count==0 || val < min) { 
            min = val; 
        } 
  
        st.Push(val * demoVal 
                + min); // encode the current value with 
                        // demoVal, combine with min and 
                        // insert into stack 
        Console.WriteLine("pushed: " + val); 
    } 
  
    int pop() 
    {     
        // if stack is empty return -1; 
        if (st.Count==0 ) { 
             Console.WriteLine("stack underflow");  
               return -1; 
          } 
        
        int val = st.Pop(); 
  
        if (st.Count!=0) // if stack is empty, there would 
                           // be no min value present, so 
                           // make min as -1 
            min = st.Peek() % demoVal; 
        else
            min = -1; 
        Console.WriteLine("popped: " + val / demoVal); 
        return val / demoVal; // decode actual value from 
                              // encoded value 
    } 
  
    int peek() 
    { 
        return st.Peek() / demoVal; // decode actual value 
                                    // from encoded value 
    } 
  
    // Driver Code 
    public static void Main(String[] args) 
    { 
        SpecialStack s = new SpecialStack(); 
  
        int[] arr = { 3, 2, 6, 1, 8, 5, 5, 5, 5 }; 
  
        for (int i = 0; i < arr.Length; i++) { 
            s.push(arr[i]); 
            s.getMin(); 
        } 
        Console.WriteLine(); 
        for (int i = 0; i < arr.Length; i++) { 
            s.pop(); 
            s.getMin(); 
        } 
    } 
} 
  
// This code is contributed by gauravrajput1 

Javascript

/* A special stack having peek() pop() and 
 * push() along with additional getMin() that 
 * returns minimum value in a stack without  
 * using extra space and all operations in O(1) 
 * time.. ???? */
  
class SpecialStack 
{ 
    constructor(){ 
        // Sentinel value for min 
        this.min = -1; 
          
        // Demo value 
        this.demoVal = 9999; 
        this.st = []; 
    } 
  
    getMin() 
    { 
        console.log("min is: ", this.min); 
    } 
  
    push(val) 
    { 
          
        // If stack is empty OR current element  
        // is less than min, update min. 
        if ((this.st.length == 0) || (val < this.min)) 
        { 
            this.min = val; 
        } 
          
        // Encode the current value with 
        // demoVal, combine with min and 
        // insert into stack 
        this.st.push(val * this.demoVal + this.min);  
        console.log("pushed: ", val); 
    } 
  
    pop() 
    {     
        // if stack is empty return -1; 
        if (this.st.length == 0) { 
            console.log("stack underflow"); 
            return -1; 
        } 
        
        let val = this.st[this.st.length - 1]; 
        this.st.pop(); 
          
        // If stack is empty, there would 
        // be no min value present, so 
        // make min as -1 
        if (this.st.length){ 
            this.min = this.st[this.st.length - 1]% this.demoVal; 
        } 
        else{ 
            this.min = -1; 
        } 
              
        console.log("popped: ", Math.floor(val / this.demoVal)); 
          
        // Decode actual value from 
        // encoded value 
        return Math.floor(val / this.demoVal);  
    } 
  
    peek() 
    { 
          
        // Decode actual value 
        // from encoded value 
        return Math.floor(this.st[this.st.length - 1] / demoVal);  
    } 
}; 
  
// Driver Code 
let s = new SpecialStack(); 
  
let arr = [3, 2, 6, 1, 8, 5, 5, 5, 5 ]; 
  
for(let i = 0; i < arr.length; i++) 
{ 
    s.push(arr[i]); 
    s.getMin(); 
} 
  
console.log(); 
  
for(let i = 0; i < arr.length; i++) 
{ 
    s.pop(); 
    s.getMin(); 
} 
  
  
// This code is contributed by Nidhi goel.  

Output

pushed: 3
min is: 3
pushed: 2
min is: 2
pushed: 6
min is: 2
pushed: 1
min is: 1
pushed: 8
min is: 1
pushed: 5
min is: 1
pushed: 5
min is: 1
pushed: 5
min is: 1
pushed: 5
min is: 1

popped: 5
min is: 1
popped: 5
min is: 1
popped: 5
min is: 1
popped: 5
min is: 1
popped: 8
min is: 1
popped: 1
min is: 2
popped: 6
min is: 2
popped: 2
min is: 3
popped: 3
min is: -1

Complexity Analysis:

For push() operation: O(1) (As insertion ‘push’ in a stack takes constant time)
For pop() operation: O(1) (As pop operation in a stack takes constant time)

For ‘Get Min’ operation: O(1) (As we have maintained min variable throughout the code)

Auxiliary Space: O(1). No extra space is used.

Design a stack that supports getMin() in O(1) time and O(1) extra space
Thanks to @Venki, @swarup, and @Jing Huang for their inputs.
Please write comments if you find the above code incorrect, or find other ways to solve the same problem.

GeeksforGeeks

Improve

Previous Article

Stack in Scala

Implement two Stacks in an Array

Similar Reads

Longest Common Substring (Space optimized DP solution)

Given two strings 'X' and 'Y', find the length of longest common substring. Expected space complexity is linear.Examples : Input : X = "GeeksforGeeks", Y = "GeeksQuiz" Output : 5 The longest common substring is "Geeks" and is of length 5. Input : X = "abcdxyz", Y = "xyzabcd" Output : 4 The longest common substring is "abcd" and is of length 4. We h

Number of n digit stepping numbers | Space optimized solution

Given n, find the count of n digit Stepping numbers. A number is called a stepping number if all adjacent digits have an absolute difference of 1. 321 is a Stepping Number while 421 is not.Examples: Input : 2 Output : 17 The numbers are 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98. Input : 1 Output : 10 The numbers are 0, 1, 2

Print Longest Bitonic subsequence (Space Optimized Approach)

Given an array arr[] of size N, the task is to print the longest bitonic subsequence of the given array.Note: If more than one solution exit then prints anyone solution. Examples: Input: arr[] = {1, 11, 2, 10, 4, 5, 2, 1} Output: 1 11 10 5 2 1 Explanation: All possible longest bitonic subsequences from the above array are {1, 2, 10, 4, 2, 1}, {1, 1

Word Wrap problem ( Space optimized solution )

Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. Assume that the length of each word is smaller than the line width. When line breaks are inserted there is a possibility that extra spaces are present in each line

Printing Matrix Chain Multiplication (A Space Optimized Solution)

Prerequisite : Dynamic Programming | Set 8 (Matrix Chain Multiplication)Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. We have many options to multiply a chain of matrices be

A Space Optimized Solution of LCS

Given two strings, find the length of the longest subsequence present in both of them. Examples: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. We have discussed a typical dynamic programming-based solution for LCS. We can optimize the space used by LCS probl

A Space Optimized DP solution for 0-1 Knapsack Problem

Given the weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the max

Vertical Sum in Binary Tree | Set 2 (Space Optimized)

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical linesVertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes

Implement Dynamic Multi Stack (K stacks) using only one Data Structure

In this article, we will see how to create a data structure that can handle multiple stacks with growable size. The data structure needs to handle three operations: push(x, stackNum) = pushes value x to the stack numbered stackNumpop(stackNum) = pop the top element from the stack numbered stackNumtop(stackNum) = shows the topmost element of the sta

Design a stack to retrieve original elements and return the minimum element in O(1) time and O(1) space

Our task is to design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be performed with time complexity O(1). To implement SpecialStack, you should onl

Article Tags :

Practice Tags :