Design a stack that supports getMin() in O(1) time and O(1) extra space

Last Updated : 17 Apr, 2023

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 have a time and space complexity of O(1).
Note: To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, lists, etc

Example:

Input: 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.

Approach: To solve the problem follow the below idea:

We define a variable minEle that stores the current minimum element in the stack. Now the interesting part is, how to handle the case when the minimum element is removed. To handle this, we push “2x – minEle” into the stack instead of x so that the previous minimum element can be retrieved using the current minEle and its value stored in the stack

Follow the given steps to implement the stack operations:

Push(x): Insert x at the top of the stack

If the stack is empty, insert x into the stack and make minEle equal to x.
If the stack is not empty, compare x with minEle. Two cases arise:
- If x is greater than or equal to minEle, simply insert x.
- If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x.
  For example, let the previous minEle be 3. Now we want to insert 2. We update minEle as 2 and insert 2*2 – 3 = 1 into the stack

Pop(): Removes an element from the top of the stack

Remove the element from the top. Let the removed element be y. Two cases arise:
- If y is greater than or equal to minEle, the minimum element in the stack is still minEle.
- If y is less than minEle, the minimum element now becomes (2*minEle – y), so update (minEle = 2*minEle – y). This is where we retrieve the previous minimum from the current minimum and its value in the stack.
  For example, let the element to be removed be 1 and minEle be 2. We remove 1 and update minEle as 2*2 – 1 = 3

Important Points:

Stack doesn’t hold the actual value of an element if it is minimum so far.

The actual minimum element is always stored in the minEle variable

Below is the illustration of the above approach:

Push(x)

Number to be Inserted: 3, Stack is empty, so insert 3 into stack and minEle = 3.

Number to be Inserted: 5, Stack is not empty, 5> minEle, insert 5 into stack and minEle = 3.

Number to be Inserted: 2, Stack is not empty, 2< minEle, insert (2*2-3 = 1) into stack and minEle = 2.

Number to be Inserted: 1, Stack is not empty, 1< minEle, insert (2*1-2 = 0) into stack and minEle = 1.

Number to be Inserted: 1, Stack is not empty, 1 = minEle, insert 1 into stack and minEle = 1.

Number to be Inserted: -1, Stack is not empty, -1 < minEle, insert (2*-1 – 1 = -3) into stack and minEle = -1.

Pop()

Initially the minimum element minEle in the stack is -1.

Number removed: -3, Since -3 is less than the minimum element the original number being removed is minEle which is -1, and the new minEle = 2*-1 – (-3) = 1

Number removed: 1, 1 == minEle, so number removed is 1 and minEle is still equal to 1.

Number removed: 0, 0< minEle, original number is minEle which is 1 and new minEle = 2*1 – 0 = 2.

Number removed: 1, 1< minEle, original number is minEle which is 2 and new minEle = 2*2 – 1 = 3.

Number removed: 5, 5> minEle, original number is 5 and minEle is still 3

Below is the implementation of the above approach:

C++

// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
 
// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack {
    stack<int> s;
    int minEle;
 
    // Prints minimum element of MyStack
    void getMin()
    {
        if (s.empty())
            cout << "Stack is empty\n";
 
        // variable minEle stores the minimum element
        // in the stack.
        else
            cout << "Minimum Element in the stack is: "
                 << minEle << "\n";
    }
 
    // Prints top element of MyStack
    void peek()
    {
        if (s.empty()) {
            cout << "Stack is empty ";
            return;
        }
 
        int t = s.top(); // Top element.
 
        cout << "Top Most Element is: ";
 
        // If t < minEle means minEle stores
        // value of t.
        (t < minEle) ? cout << minEle : cout << t;
    }
 
    // Remove the top element from MyStack
    void pop()
    {
        if (s.empty()) {
            cout << "Stack is empty\n";
            return;
        }
 
        cout << "Top Most Element Removed: ";
        int t = s.top();
        s.pop();
 
        // Minimum will change as the minimum element
        // of the stack is being removed.
        if (t < minEle) {
            cout << minEle << "\n";
            minEle = 2 * minEle - t;
        }
 
        else
            cout << t << "\n";
    }
 
    // Removes top element from MyStack
    void push(int x)
    {
        // Insert new number into the stack
        if (s.empty()) {
            minEle = x;
            s.push(x);
            cout << "Number Inserted: " << x << "\n";
            return;
        }
 
        // If new number is less than minEle
        else if (x < minEle) {
            s.push(2 * x - minEle);
            minEle = x;
        }
 
        else
            s.push(x);
 
        cout << "Number Inserted: " << x << "\n";
    }
};
 
// Driver Code
int main()
{
    MyStack s;
   
      // Function calls
    s.push(3);
    s.push(5);
    s.getMin();
    s.push(2);
    s.push(1);
    s.getMin();
    s.pop();
    s.getMin();
    s.pop();
    s.peek();
 
    return 0;
}

Java

// Java program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
import java.util.*;
 
// A user defined stack that supports getMin() in
// addition to push() and pop()
class MyStack {
    Stack<Integer> s;
    Integer minEle;
 
    // Constructor
    MyStack() { s = new Stack<Integer>(); }
 
    // Prints minimum element of MyStack
    void getMin()
    {
        // Get the minimum number in the entire stack
        if (s.isEmpty())
            System.out.println("Stack is empty");
 
        // variable minEle stores the minimum element
        // in the stack.
        else
            System.out.println("Minimum Element in the "
                               + " stack is: " + minEle);
    }
 
    // prints top element of MyStack
    void peek()
    {
        if (s.isEmpty()) {
            System.out.println("Stack is empty ");
            return;
        }
 
        Integer t = s.peek(); // Top element.
 
        System.out.print("Top Most Element is: ");
 
        // If t < minEle means minEle stores
        // value of t.
        if (t < minEle)
            System.out.println(minEle);
        else
            System.out.println(t);
    }
 
    // Removes the top element from MyStack
    void pop()
    {
        if (s.isEmpty()) {
            System.out.println("Stack is empty");
            return;
        }
 
        System.out.print("Top Most Element Removed: ");
        Integer t = s.pop();
 
        // Minimum will change as the minimum element
        // of the stack is being removed.
        if (t < minEle) {
            System.out.println(minEle);
            minEle = 2 * minEle - t;
        }
 
        else
            System.out.println(t);
    }
 
    // Insert new number into MyStack
    void push(Integer x)
    {
        if (s.isEmpty()) {
            minEle = x;
            s.push(x);
            System.out.println("Number Inserted: " + x);
            return;
        }
 
        // If new number is less than original minEle
        if (x < minEle) {
            s.push(2 * x - minEle);
            minEle = x;
        }
 
        else
            s.push(x);
 
        System.out.println("Number Inserted: " + x);
    }
};
 
// Driver Code
public class Main {
    public static void main(String[] args)
    {
        MyStack s = new MyStack();
       
          // Function calls
        s.push(3);
        s.push(5);
        s.getMin();
        s.push(2);
        s.push(1);
        s.getMin();
        s.pop();
        s.getMin();
        s.pop();
        s.peek();
    }
}

Python 3

# Class to make a Node
class Node:
    # Constructor which assign argument to nade'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
        out = []
        while temp:
            out.append(str(temp.value))
            temp = temp.next
        out = '\n'.join(out)
        return ('Top {} \n\nStack :\n{}'.format(self.top, 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:
            print("Minimum Element in the stack is: {}" .format(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:
                print("Top Most Element is: {}" .format(self.minimum))
            else:
                print("Top Most Element is: {}" .format(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
 
        elif value < self.minimum:
            temp = (2 * value) - self.minimum
            new_node = Node(temp)
            new_node.next = self.top
            self.top = new_node
            self.minimum = value
        else:
            new_node = Node(value)
            new_node.next = self.top
            self.top = new_node
        print("Number Inserted: {}" .format(value))
 
    # This method is used to pop top of stack
    def pop(self):
        if self.top is None:
            print("Stack is empty")
        else:
            removedNode = self.top.value
            self.top = self.top.next
            if removedNode < self.minimum:
                print("Top Most Element Removed :{} " .format(self.minimum))
                self.minimum = ((2 * self.minimum) - removedNode)
            else:
                print("Top Most Element Removed : {}" .format(removedNode))
 
 
# Driver program to test above class
if __name__ == '__main__':
   
  stack = Stack()
   
  # Function calls
  stack.push(3)
  stack.push(5)
  stack.getMin()
  stack.push(2)
  stack.push(1)
  stack.getMin()
  stack.pop()
  stack.getMin()
  stack.pop()
  stack.peek()
 
# This code is contributed by Blinkii

C#

// C# program to implement a stack
// that supports getMinimum() in O(1)
// time and O(1) extra space.
using System;
using System.Collections;
 
// A user defined stack that supports
// getMin() in addition to Push() and Pop()
public class MyStack {
    public Stack s;
    public int minEle;
 
    // Constructor
    public MyStack() { s = new Stack(); }
 
    // Prints minimum element of MyStack
    public void getMin()
    {
        // Get the minimum number
        // in the entire stack
        if (s.Count == 0)
            Console.WriteLine("Stack is empty");
 
        // variable minEle stores the minimum
        // element in the stack.
        else
            Console.WriteLine("Minimum Element in the "
                              + " stack is: " + minEle);
    }
 
    // prints top element of MyStack
    public void Peek()
    {
        if (s.Count == 0) {
            Console.WriteLine("Stack is empty ");
            return;
        }
 
        int t = (int)s.Peek(); // Top element.
 
        Console.Write("Top Most Element is: ");
 
        // If t < minEle means minEle stores
        // value of t.
        if (t < minEle)
            Console.WriteLine(minEle);
        else
            Console.WriteLine(t);
    }
 
    // Removes the top element from MyStack
    public void Pop()
    {
        if (s.Count == 0) {
            Console.WriteLine("Stack is empty");
            return;
        }
 
        Console.Write("Top Most Element Removed: ");
        int t = (int)s.Pop();
 
        // Minimum will change as the minimum element
        // of the stack is being removed.
        if (t < minEle) {
            Console.WriteLine(minEle);
            minEle = 2 * minEle - t;
        }
 
        else
            Console.WriteLine(t);
    }
 
    // Insert new number into MyStack
    public void Push(int x)
    {
        if (s.Count == 0) {
            minEle = x;
            s.Push(x);
            Console.WriteLine("Number Inserted: " + x);
            return;
        }
 
        // If new number is less than original minEle
        if (x < minEle) {
            s.Push(2 * x - minEle);
            minEle = x;
        }
 
        else
            s.Push(x);
 
        Console.WriteLine("Number Inserted: " + x);
    }
}
 
// Driver Code
public class main {
    public static void Main(String[] args)
    {
        MyStack s = new MyStack();
       
          // Function calls
        s.Push(3);
        s.Push(5);
        s.getMin();
        s.Push(2);
        s.Push(1);
        s.getMin();
        s.Pop();
        s.getMin();
        s.Pop();
        s.Peek();
    }
}
 
// This code is contributed by Arnab Kundu

Javascript

// JS program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
 
// A user defined stack that supports getMin() in
// addition to push() and pop()
class MyStack {
    constructor() {
        this.s = [];
        this.minEle;
    }
 
    // Prints minimum element of MyStack
    getMin() {
        if (this.s.length == 0)
            console.log("Stack is empty");
 
        // variable minEle stores the minimum element
        // in the stack.
        else
            console.log("Minimum Element in the stack is: ", this.minEle);
    }
 
    // Prints top element of MyStack
    peek() {
        if (this.s.length == 0) {
            console.log("Stack is empty ");
            return;
        }
        let t = this.s[0]; // Top element.
 
        console.log("Top Most Element is: ");
 
        // If t < minEle means minEle stores
        // value of t.
        (t < this.minEle) ? console.log(this.minEle) : console.log(t);
 
    }
 
    // Remove the top element from MyStack
    pop() {
        if (this.s.length == 0) {
            console.log("Stack is empty ");
            return;
        }
        console.log("Top Most Element Removed: ");
        let t = this.s[0]; // Top element.
        this.s.shift();
 
        // Minimum will change as the minimum element
        // of the stack is being removed.
        if (t < this.minEle) {
            console.log(this.minEle);
            this.minEle = (2 * this.minEle) - t;
        }
 
        else
            console.log(t);
    }
 
    // Removes top element from MyStack
    push(x) {
        // Insert new number into the stack
        if (this.s.length == 0) {
            this.minEle = x;
            this.s.unshift(x);
            console.log("Number Inserted: ", x);
            return;
        }
 
        // If new number is less than minEle
        else if (x < this.minEle) {
            this.s.unshift(2 * x - this.minEle);
            this.minEle = x;
        }
 
        else
            this.s.unshift(x);
 
        console.log("Number Inserted: ", x);
    }
 
 
};
 
 
// Driver Code
let s = new MyStack;
 
// Function calls
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
 
// This code is contributed by adityamaharshi21

Output

Number Inserted: 3
Number Inserted: 5
Minimum Element in the stack is: 3
Number Inserted: 2
Number Inserted: 1
Minimum Element in the stack is: 1
Top Most Element Removed: 1
Minimum Element in the stack is: 2
Top Most Element Removed: 2
Top Most Element is: 5

Time Complexity: O(1)
Auxiliary Space: O(1)

How does this approach work?

When the element to be inserted is less than minEle, we insert “2x – minEle”. The important thing to note is, that 2x – minEle will always be less than x (proved below), i.e., new minEle and while popping out this element we will see that something unusual has happened as the popped element is less than the minEle. So we will be updating minEle.

How 2*x – minEle is less than x in push()?

x < minEle which means x – minEle < 0

// Adding x on both sides
x – minEle + x < 0 + x
2*x – minEle < x
We can conclude 2*x – minEle < new minEle

While popping out, if we find the element(y) less than the current minEle, we find the new minEle = 2*minEle – y

How previous minimum element, prevMinEle is, 2*minEle – y
in pop() is y the popped element?

// We pushed y as 2x – prevMinEle. Here
// prevMinEle is minEle before y was inserted

y = 2*x – prevMinEle

// Value of minEle was made equal to x
minEle = x .

new minEle = 2 * minEle – y
= 2*x – (2*x – prevMinEle)
= prevMinEle // This is what we wanted

Design a stack that supports getMin() in O(1) time and O(1) extra space by creating a MinStack class:

To solve the problem follow the below idea:

Create a class node that has two variables Val and min. Val will store the actual value that we are going to insert in the stack, whereas min will store the min value so far seen up to that node

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int mini(int a, int b) { return a > b ? b : a; }
 
class MinStack {
public:
    stack<pair<int, int> > s;
 
    void push(int element)
    {
        /* new max will be given no. if stack is empty else
        we compare given no. to max at current top of
        stack*/
 
        int new_min = s.empty()
                          ? element
                          : mini(element, s.top().second);
 
        // we push the pair of given_element,new_min in s
 
        s.push({ element, new_min });
    }
 
    int pop()
    {
        int popped;
        if (!s.empty()) {
            // popped has popped number
            popped = s.top().first;
            s.pop();
        }
        else {
            // print a message or throw exception etc
        }
        return popped;
    }
 
    int minimum()
    {
        int min_elem = s.top().second;
        return min_elem;
    }
};
 
// Driver code
int main()
{
    MinStack s;
 
    // Function calls
    s.push(-1);
    s.push(10);
    s.push(-4);
    s.push(0);
    cout << s.minimum() << endl;
    cout << s.pop() << endl;
    cout << s.pop() << endl;
    cout << s.minimum();
    return 0;
}
 
// this code is contributed by Apoorv Shrivastava - VITB

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
class MinStack {
    Stack<Node> s;
 
    class Node {
        int val;
        int min;
        public Node(int val, int min)
        {
            this.val = val;
            this.min = min;
        }
    }
 
    /** initialize your data structure here. */
    public MinStack() { this.s = new Stack<Node>(); }
    public void push(int x)
    {
        if (s.isEmpty()) {
            this.s.push(new Node(x, x));
        }
        else {
            int min = Math.min(this.s.peek().min, x);
            this.s.push(new Node(x, min));
        }
    }
    public int pop() { return this.s.pop().val; }
    public int top() { return this.s.peek().val; }
    public int getMin() { return this.s.peek().min; }
}
 
// Driver code
class GFG {
 
    public static void main(String[] args)
    {
        MinStack s = new MinStack();
       
          // Function calls
        s.push(-1);
        s.push(10);
        s.push(-4);
        s.push(0);
        System.out.println(s.getMin());
        System.out.println(s.pop());
        System.out.println(s.pop());
        System.out.println(s.getMin());
    }
}
// this code is contributed by gireeshgudaparthi

Python3

# Python program for the above approach
class MinStack:
   
    # initialize your data structure here.
    def __init__(self):
        self.s = []
 
    class Node:
        def __init__(self, val, Min):
            self.val = val
            self.min = Min
 
    def push(self, x):
        if not self.s:
            self.s.append(self.Node(x, x))
        else:
            Min = min(self.s[-1].min, x)
            self.s.append(self.Node(x, Min))
 
    def pop(self):
        return self.s.pop().val
 
    def top(self):
        return self.s[-1].val
 
    def getMin(self):
        return self.s[-1].min
 
s = MinStack()
 
# Function calls
s.push(-1)
s.push(10)
s.push(-4)
s.push(0)
print(s.getMin())
print(s.pop())
print(s.pop())
print(s.getMin())
 
# This code is contributed by lokesh

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class MinStack {
    Stack<Node> s;
 
    public class Node {
        public int val;
        public int min;
 
        public Node(int val, int min)
        {
            this.val = val;
            this.min = min;
        }
    }
 
    /** initialize your data structure here. */
    public MinStack() { this.s = new Stack<Node>(); }
 
    public void push(int x)
    {
        if (s.Count == 0) {
            this.s.Push(new Node(x, x));
        }
        else {
            int min = Math.Min(this.s.Peek().min, x);
            this.s.Push(new Node(x, min));
        }
    }
 
    public int pop() { return this.s.Pop().val; }
 
    public int top() { return this.s.Peek().val; }
 
    public int getMin() { return this.s.Peek().min; }
}
 
// Driver code
public class GFG {
 
    public static void Main(String[] args)
    {
        MinStack s = new MinStack();
       
          // Function call
        s.push(-1);
        s.push(10);
        s.push(-4);
        s.push(0);
        Console.WriteLine(s.getMin());
        Console.WriteLine(s.pop());
        Console.WriteLine(s.pop());
        Console.WriteLine(s.getMin());
    }
}
 
// This code contributed by gauravrajput1

Javascript

// JS program for the above approach
 
function mini(a,b) { return a > b ? b : a; }
 
class MinStack {
    constructor()
    {
        this.s = new Array();
    }
 
    pushE(element)
    {
        /* new max will be given no. if stack is empty else
        we compare given no. to max at current top of
        stack*/
         
        let new_min = 0;
        if(this.s.length==0)
            new_min = element;
        else
            new_min = mini(element,this.s[this.s.length-1].second);
         
        // we push the pair of given_element,new_min in s
        this.s.push({
            first:element,
            second:new_min
        });
    }
 
    popE()
    {
        let popped;
        if (this.s.length>0) {
            // popped has popped number
            popped = this.s[this.s.length-1].first;
            this.s.pop();
        }
        else {
            // print a message or throw exception etc
        }
        return popped;
    }
 
    minimum()
    {
        let min_elem = this.s[this.s.length-1].second;
        return min_elem;
    }
};
 
// Driver code
let s = new MinStack();
 
// Function calls
s.pushE(-1);
s.pushE(10);
s.pushE(-4);
s.pushE(0);
console.log(s.minimum());
console.log(s.popE());
console.log(s.popE());
console.log(s.minimum());
 
// This code is contributed by adityamaharshi21

Output

-4
0
-4
-1

Related Article: An approach that uses O(1) time and O(n) extra space is discussed here.

N

Nikhil Tekwani

Improve

Previous Article

How to efficiently implement k stacks in a single array?

Implement a stack using single queue

Similar Reads

Design a dynamic stack using arrays that supports getMin() in O(1) time and O(1) extra space

Design a special dynamic Stack using an array that supports all the stack operations such as push(), pop(), peek(), isEmpty(), and getMin() operations in constant Time and Space complexities. Examples: Assuming the right to left orientation as the top to bottom orientation and performing the operations: Push(10): 10 is added to the top of the stack

Find maximum in a stack in O(1) time and O(1) extra space

Given a stack of integers. The task is to design a special stack such that the maximum element can be found in O(1) time and O(1) extra space. Examples: Given Stack : 2 5 1 64 --> Maximum So Output must be 64 when getMax() is called. Below are the different functions designed to push and pop elements from the stack. Push(x) : Inserts x at the to

Design a structure which supports insertion and first non-repeating element in O(1) time

Design a Data structure which supports insertion and first non-repeating element in O(1) time. Operations that are supported by the data structure: Insertion: Insert a element into the data structure.First non-repeating Element: First non-repeating element into the array. Note: If there is no non-repeating element in the array then print -1. Consid

Design a data structure that supports insert, delete, search and getRandom in constant time

Design a data structure that supports the following operations in O(1) time. insert(x): Inserts an item x to the data structure if not already present.remove(x): Removes item x from the data structure if present. search(x): Searches an item x in the data structure.getRandom(): Returns a random element from the current set of elements We can use has

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

Clone a stack without using extra space | Set 2

Given a stack S, the task is to copy the content of the given stack S to another stack T maintaining the same order. Examples: Input: Source:- |5| |4| |3| |2| |1|Output: Destination:- |5| |4| |3| |2| |1| Input: Source:- |12| |13| |14| |15| |16|Output: Destination:- |12| |13| |14| |15| |16| Reversing the Stack-Based Approach: Please refer to the pre

Clone a stack without extra space

Given a source stack, copy the contents of the source stack to the destination stack maintaining the same order without using extra space. Examples: Input : Source:- |3| |2| |1|Output : Destination:- |3| |2| |1|Input : Source:- |a| |b| |c|Output : Destination:- |a| |b| |c|Approach: In order to solve this without using extra space, we first reverse

Reverse a stack without using extra space in O(n)

Reverse a Stack without using recursion and extra space. Even the functional Stack is not allowed. Examples: Input : 1->2->3->4 Output : 4->3->2->1 Input : 6->5->4 Output : 4->5->6 We have discussed a way of reversing a stack in the below post.Reverse a Stack using Recursion The above solution requires O(n) extra space

Java Program for Rearrange positive and negative numbers in O(n) time and O(1) extra space

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in t

Python Program to Rearrange positive and negative numbers in O(n) time and O(1) extra space

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in t

Article Tags :

Practice Tags :