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 only use standard Stack data structure and no other data structure like arrays, list etc.
Example:
Consider the following Special-Stack 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.
An approach that uses O(1) time and O(1) extra space is discussed here. However, in the previous article the original elements are not recovered. Only the minimum element is returned at any given point of time.
In this article, the previous approach is modified so that original elements can also be retrieved during a pop() operation.
Approach:
Consider a variable minimum in which we store the minimum element in the stack. Now, what if we pop the minimum element from the stack? How do we update the minimum variable to the next minimum value? One solution is to maintain another stack in sorted order so that the smallest element is always on the top. However, this is an O(n) space approach.
To achieve this in O(1) space, we need a way to store the current value of an element and the next minimum value in the same node. This can be done by applying simple mathematics:
new_value = 2*current_value - minimum
We push this new_value into the stack instead of current_value. To retrieve current_value and next minimum from new_value:
current_value = (new_value + minimum)/2 minimum = new_value - 2*current
When the operation Push(x) is done, we follow the given below algorithm:
- If stack is empty
- insert x into the stack
- make minimum equal to x.
- If stack is not empty
- if x is less than minimum
- set temp equal to 2*x-minimum
- set minimum equal to x
- set x equal to temp
- insert x into stack
When the operation Pop(x) is done, we follow the given below algorithm:
- If stack is not empty
- set x equal to topmost element
- if x is less than minimum
- set minimum equal to 2*minimum – x
- set x equal to (x+minimum)/2
- return x
When getMin() is called, we return the element stored in variable, minimum:
Implementation:
C++
// Cpp program to retrieve original elements of the // from a Stack which returns the minimum element // in O(1) time and O(1) space #include<bits/stdc++.h> using namespace std; // Node class which contains data // and pointer to next node class Node { public : int data; Node* next; Node() { data = -1; next = NULL; } Node( int d) { data = d; next = NULL; } void setData( int data) { this ->data = data; } void setNext(Node* next) { this ->next = next; } Node* getNext() { return next; } int getData() { return data; } }; class Stack{ public : Node* top; // Stores minimum element of the stack int minimum; // Function to push an element void push(Node* node) { int current=node->getData(); if (top == NULL) { top=node; minimum=current; } else { if (current < minimum) { node->setData(2*current - minimum); minimum = current; } node->setNext(top); top=node; } } // Retrieves topmost element Node* pop() { Node* node = top; if (node!=NULL) { int current=node->getData(); if (current<minimum) { minimum = 2*minimum - current; node->setData((current + minimum) / 2); } top = top->getNext(); } return node; } // Retrieves topmost element without // popping it from the stack Node* peek() { Node* node = NULL; if (top != NULL) { node = new Node(); int current = top->getData(); node->setData(current < minimum ? minimum : current); } return node; } // Function to print all elements in the stack void printAll() { Node* ptr = top; int min = minimum; if (ptr != NULL) { // if stack is not empty while ( true ) { int val = ptr->getData(); if (val < min) { min = 2 * min - val; val = (val + min) / 2; } cout << val << " " ; ptr = ptr->getNext(); if (ptr == NULL) break ; } cout << '\n' ; } else cout << "Empty!\n" ; } // Returns minimum of Stack int getMin() { return minimum; } bool isEmpty() { return top == NULL; } }; int main() { Stack* stack = new Stack(); Node* node; stack->push( new Node(5)); stack->push( new Node(3)); stack->push( new Node(4)); // Calls the method to print the stack cout << "Elements in the stack are:\n" ; stack->printAll(); // Print current minimum element if stack is // not empty if (stack->isEmpty()) cout << "Empty Stack!\n" ; else cout << "Minimum: " << stack->getMin() << '\n' ; // Push new elements into the stack stack->push( new Node(1)); stack->push( new Node(2)); // Printing the stack cout << "Stack after adding new elements:\n" ; stack->printAll(); // Print current minimum element if stack is // not empty if (stack->isEmpty()) cout << "Empty Stack!\n" ; else cout << "Minimum: " << stack->getMin() << '\n' ; // Pop elements from the stack node = stack->pop(); cout << "Element Popped: " ; if (node == NULL) cout << "Empty!\n" ; else cout << node->getData() << '\n' ; node = stack->pop(); cout << "Element Popped: " ; if (node == NULL) cout << "Empty!\n" ; else cout << node->getData() << '\n' ; // Printing stack after popping elements cout << "Stack after removing top two elements:\n" ; stack->printAll(); // Printing current Minimum element in the stack if (stack->isEmpty()) cout << "Empty Stack!\n" ; else cout << "Minimum: " << stack->getMin() << '\n' ; // Printing top element of the stack node = stack->peek(); cout << "Top: " ; if (node == NULL) cout << "Empty!\n" ; else cout << node->getData() << '\n' ; return 0; } |
Java
// Java program to retrieve original elements of the // from a Stack which returns the minimum element // in O(1) time and O(1) space class Stack { Node top; // Stores minimum element of the stack int minimum; // Function to push an element void push(Node node) { int current = node.getData(); if (top == null ) { top = node; minimum = current; } else { if (current < minimum) { node.setData( 2 * current - minimum); minimum = current; } node.setNext(top); top = node; } } // Retrieves topmost element Node pop() { Node node = top; if (node != null ) { int current = node.getData(); if (current < minimum) { minimum = 2 * minimum - current; node.setData((current + minimum) / 2 ); } top = top.getNext(); } return node; } // Retrieves topmost element without // popping it from the stack Node peek() { Node node = null ; if (top != null ) { node = new Node(); int current = top.getData(); node.setData(current < minimum ? minimum : current); } return node; } // Function to print all elements in the stack void printAll() { Node ptr = top; int min = minimum; if (ptr != null ) { // if stack is not empty while ( true ) { int val = ptr.getData(); if (val < min) { min = 2 * min - val; val = (val + min) / 2 ; } System.out.print(val + " " ); ptr = ptr.getNext(); if (ptr == null ) break ; } System.out.println(); } else System.out.println( "Empty!" ); } // Returns minimum of Stack int getMin() { return minimum; } boolean isEmpty() { return top == null ; } } // Node class which contains data // and pointer to next node class Node { int data; Node next; Node() { data = - 1 ; next = null ; } Node( int d) { data = d; next = null ; } void setData( int data) { this .data = data; } void setNext(Node next) { this .next = next; } Node getNext() { return next; } int getData() { return data; } } // Driver Code public class Main { public static void main(String[] args) { // Create a new stack Stack stack = new Stack(); Node node; // Push the element into the stack stack.push( new Node( 5 )); stack.push( new Node( 3 )); stack.push( new Node( 4 )); // Calls the method to print the stack System.out.println( "Elements in the stack are:" ); stack.printAll(); // Print current minimum element if stack is // not empty System.out.println(stack.isEmpty() ? "\nEmpty Stack!" : "\nMinimum: " + stack.getMin()); // Push new elements into the stack stack.push( new Node( 1 )); stack.push( new Node( 2 )); // Printing the stack System.out.println( "\nStack after adding new elements:" ); stack.printAll(); // Print current minimum element if stack is // not empty System.out.println(stack.isEmpty() ? "\nEmpty Stack!" : "\nMinimum: " + stack.getMin()); // Pop elements from the stack node = stack.pop(); System.out.println( "\nElement Popped: " + (node == null ? "Empty!" : node.getData())); node = stack.pop(); System.out.println( "Element Popped: " + (node == null ? "Empty!" : node.getData())); // Printing stack after popping elements System.out.println( "\nStack after removing top two elements:" ); stack.printAll(); // Printing current Minimum element in the stack System.out.println(stack.isEmpty() ? "\nEmpty Stack!" : "\nMinimum: " + stack.getMin()); // Printing top element of the stack node = stack.peek(); System.out.println( "\nTop: " + (node == null ? "\nEmpty!" : node.getData())); } } |
Python3
""" Python program to retrieve original elements of the from a Stack which returns the minimum element in O(1) time and O(1) space """ # Class to make a Node class Node: # Constructor which assign argument to node's value def __init__( self , value): self .value = value self . next = None # This method returns the string # representation of the object. def __str__( self ): return "Node({})" . format ( self .value) # __repr__ is same as __str__ __repr__ = __str__ class Stack: # Stack Constructor initialise # top of stack and counter. def __init__( self ): self .top = None self .count = 0 self .minimum = None # This method returns the string # representation of the object (stack). def __str__( self ): temp = self .top m = self .minimum out = [] if temp is None : print ( "Empty Stack" ) else : while not temp is None : val = temp.value if val < m: m = ( 2 * m) - val val = ( val + m ) / 2 out.append( str ( int (val))) temp = temp. next out = ' ' .join(out) return (out) # __repr__ is same as __str__ __repr__ = __str__ # This method is used to get minimum element of stack def getMin( self ): if self .top is None : return "Stack is empty" else : return self .minimum # Method to check if Stack is Empty or not def isEmpty( self ): # If top equals to None then stack is empty if self .top = = None : return True else : # If top not equal to None then stack is empty return False # This method returns length of stack def __len__( self ): self .count = 0 tempNode = self .top while tempNode: tempNode = tempNode. next self .count + = 1 return self .count # This method returns top of stack def peek( self ): if self .top is None : print ( "Stack is empty" ) else : if self .top.value < self .minimum: return self .minimum else : return self .top.value # This method is used to add node to stack def push( self ,value): if self .top is None : self .top = Node(value) self .minimum = value else : new_node = Node(value) if value < self .minimum: temp = ( 2 * value) - self .minimum new_node.value = temp self .minimum = value new_node. next = self .top self .top = new_node # This method is used to pop top of stack def pop( self ): new_node = self .top if self .top is None : print ( "Stack is empty" ) else : removedNode = new_node.value if removedNode < self .minimum: self .minimum = ( ( 2 * self .minimum ) - removedNode ) new_node.value = ( (removedNode + self .minimum) / 2 ) self .top = self .top. next return int (new_node.value) # Driver program to test above class stack = Stack() stack.push( 5 ) stack.push( 3 ) stack.push( 4 ) print ( "Elements in the stack are:" ) print (stack) print ( "Minimum: {}" . format ( stack.getMin() ) ) stack.push( 1 ) stack.push( 2 ) print ( "Stack after adding new elements:" ) print (stack) print ( "Minimum:{}" . format ( stack.getMin() ) ) print ( "Element Popped: {}" . format (stack.pop())) print ( "Element Popped: {}" . format (stack.pop())) print ( "Stack after removing top two elements: " ) print (stack) print ( "Minimum: {}" . format ( stack.getMin() ) ) print ( "Top: {}" . format ( stack.peek() ) ) # This code is contributed by Blinkii |
C#
// C# program to retrieve original elements of the // from a Stack which returns the minimum element // in O(1) time and O(1) space using System; public class Stack { Node top; // Stores minimum element of the stack public int minimum; // Function to push an element public void push(Node node) { int current = node.getData(); if (top == null ) { top = node; minimum = current; } else { if (current < minimum) { node.setData(2 * current - minimum); minimum = current; } node.setNext(top); top = node; } } // Retrieves topmost element public Node pop() { Node node = top; if (node != null ) { int current = node.getData(); if (current < minimum) { minimum = 2 * minimum - current; node.setData((current + minimum) / 2); } top = top.getNext(); } return node; } // Retrieves topmost element without // popping it from the stack public Node peek() { Node node = null ; if (top != null ) { node = new Node(); int current = top.getData(); node.setData(current < minimum ? minimum : current); } return node; } // Function to print all elements in the stack public void printAll() { Node ptr = top; int min = minimum; if (ptr != null ) { // if stack is not empty while ( true ) { int val = ptr.getData(); if (val < min) { min = 2 * min - val; val = (val + min) / 2; } Console.Write(val + " " ); ptr = ptr.getNext(); if (ptr == null ) break ; } Console.WriteLine(); } else Console.WriteLine( "Empty!" ); } // Returns minimum of Stack public int getMin() { return minimum; } public bool isEmpty() { return top == null ; } } // Node class which contains data // and pointer to next node public class Node { public int data; public Node next; public Node() { data = -1; next = null ; } public Node( int d) { data = d; next = null ; } public void setData( int data) { this .data = data; } public void setNext(Node next) { this .next = next; } public Node getNext() { return next; } public int getData() { return data; } } // Driver Code public class MainClass { public static void Main(String[] args) { // Create a new stack Stack stack = new Stack(); Node node; // Push the element into the stack stack.push( new Node(5)); stack.push( new Node(3)); stack.push( new Node(4)); // Calls the method to print the stack Console.WriteLine( "Elements in the stack are:" ); stack.printAll(); // Print current minimum element if stack is // not empty Console.WriteLine(stack.isEmpty() ? "\nEmpty Stack!" : "\nMinimum: " + stack.getMin()); // Push new elements into the stack stack.push( new Node(1)); stack.push( new Node(2)); // Printing the stack Console.WriteLine( "\nStack after adding new elements:" ); stack.printAll(); // Print current minimum element if stack is // not empty Console.WriteLine(stack.isEmpty() ? "\nEmpty Stack!" : "\nMinimum: " + stack.getMin()); // Pop elements from the stack node = stack.pop(); if (node == null ) Console.WriteLine( "\nElement Popped: " + "Empty!" ); else Console.WriteLine( "\nElement Popped: " +node.getData()); node = stack.pop(); if (node == null ) Console.WriteLine( "Element Popped: " + "Empty!" ); else Console.WriteLine( "Element Popped: " +node.getData()); // Printing stack after popping elements Console.WriteLine( "\nStack after removing top two elements:" ); stack.printAll(); // Printing current Minimum element in the stack Console.WriteLine(stack.isEmpty() ? "\nEmpty Stack!" : "\nMinimum: " + stack.getMin()); // Printing top element of the stack node = stack.peek(); if (node == null ) Console.WriteLine( "\nTop: " + "\nEmpty!" ); else Console.WriteLine( "\nTop: " +node.getData()); } } // This code is contributed by Rajput-Ji |
Javascript
// Class to make a Node class Node { // Constructor which assign argument to node's value constructor(value) { this .value = value; this .next = null ; } // This method returns the string // representation of the object. toString() { return `Node(${ this .value})`; } } class Stack { // Stack Constructor initialise // top of stack and counter. constructor() { this .top = null ; this .count = 0; this .minimum = null ; } // This method returns the string // representation of the object (stack). toString() { let temp = this .top; let m = this .minimum; let out = []; if (temp === null ) { console.log( "Empty Stack" ); } else { while (temp !== null ) { let val = temp.value; if (val < m) { m = 2 * m - val; val = (val + m) / 2; } out.push(Math.floor(val)); temp = temp.next; } out = out.join( " " ); return out; } } // This method is used to get minimum element of stack getMin() { if ( this .top === null ) { return "Stack is empty" ; } else { return this .minimum; } } // Method to check if Stack is Empty or not isEmpty() { // If top equals to None then stack is empty if ( this .top === null ) { return true ; } else { // If top not equal to None then stack is not empty return false ; } } // This method returns length of stack length() { this .count = 0; let tempNode = this .top; while (tempNode) { tempNode = tempNode.next; this .count++; } return this .count; } // This method returns top of stack peek() { if ( this .top === null ) { console.log( "Stack is empty" ); } else { if ( this .top.value < this .minimum) { return this .minimum; } else { return this .top.value; } } } // This method is used to add node to stack push(value) { if ( this .top === null ) { this .top = new Node(value); this .minimum = value; } else { let new_node = new Node(value); if (value < this .minimum) { let temp = 2 * value - this .minimum; new_node.value = temp; this .minimum = value; } new_node.next = this .top; this .top = new_node; } } // This method is used to pop top of stack pop() { let new_node = this .top; if ( this .top === null ) { console.log( "Stack is empty" ); } else { let removedNode = new_node.value; if (removedNode < this .minimum) { this .minimum = 2 * this .minimum - removedNode; new_node.value = (removedNode + this .minimum) / 2; } this .top = this .top.next; return Math.floor(new_node.value); } } } // Driver program to test above class let stack = new Stack(); stack.push(5); stack.push(3); stack.push(4); console.log( "Elements in the stack are:" ); console.log(stack.toString()); console.log(`Minimum: ${stack.getMin()}`); stack.push(1); stack.push(2); console.log( "Stack after adding new elements:" ); console.log(stack.toString()); console.log(`Minimum: ${stack.getMin()}`); console.log(`Element Popped: ${stack.pop()}`); console.log(`Element Popped: ${stack.pop()}`); console.log( "Stack after removing top two elements: " ); console.log(stack.toString()); console.log(`Minimum: ${stack.getMin()}`); console.log(`Top: ${stack.peek()}`); // This code is contributed by sdeadityasharma |
Elements in the stack are: 4 3 5 Minimum: 3 Stack after adding new elements: 2 1 4 3 5 Minimum: 1 Element Popped: 2 Element Popped: 1 Stack after removing top two elements: 4 3 5 Minimum: 3 Top: 4