Thursday, July 4, 2019

Get minimum element from stack in O(1) time

Problem Statement:

You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.
Input:
The first line of the input contains an integer 'T' denoting the number of test cases. Then T test cases follow. First line of each test case contains an integer Q denoting the number of queries.
A Query Q may be of 3 Types:
    1. 1 x (a query of this type means  pushing 'x' into the stack)
    2. 2 (a query of this type means to pop element from stack and print the poped element)
    3. 3 (a query of this type means to print the minimum element from the stack)
The second line of each test case contains Q queries seperated by space.

Output:
The output for each test case will  be space separated integers having -1 if the stack is empty else the element poped out  or min element from the stack.

User Task:
You are required to complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer poped out from the stack and getMin() which returns the min element from the stack.

Constraints:
1 <= T <= 100
1 <= Q <= 100
1 <= x <= 100

Example:
Input:

1
6
1 2 1 3 2 3 1 1 3   

Output:
3 2 1

Explanation:
Testcase 1:
In the first test case for query
1 2  the stack will be {2}
1 3  the stack will be {2 3}
2 poped element will be 3 the stack will be {2}
3 min element will be 2
1 1 the stack will be {2 1}
3 min element will be 1


Solution: 


import java.util.*;
class Get_Min_From_Stack
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T>0)
        {
            int q = sc.nextInt();
            MuscleJava g = new MuscleJava();
            while(q>0)
            {
                int qt = sc.nextInt();
               
                if(qt == 1)
                {
                    int att = sc.nextInt();
                    g.push(att);
                }
                else if(qt == 2)
                {
                    System.out.print(g.pop()+" ");
                }
                else if(qt == 3)
                {
                    System.out.print(g.getMin()+" ");
                }
           
            q--;
            }
            System.out.println();
        T--;
        }
       
    }
}
class MuscleJava
{
    int minEle; 

    Stack<Integer> s = new Stack();
    // System.out.println("Statck " + s);
    /*returns min element from stack*/
    int getMin()
    {
        if(s.isEmpty() )
            return -1;
        return minEle;
    }
   
    /*returns poped element from stack*/
    int pop()
    {
        if(s.size() == 0 )
            return -1;
        else if(s.peek() >= minEle)
            return s.pop();
        else
        {
            minEle = 2*minEle - s.pop();
            return (minEle);
        }
    }
    /*push element x into the stack*/
    void push(int x)
    {
        if( s.isEmpty() )
        {
            s.push(x);
            minEle = x;
        }
        else if(x < minEle)
        {
            int prevMin = minEle;
            minEle = x;
            s.push(((2*minEle) - prevMin));
        }
        else
            s.push(x);
    }   
}

No comments:

Post a Comment