Great Work

Hi, your idea is cool!

+

1. We can stack max elements only
2. We can store count of elements that less than max and that have been pushed after max

StackNode {
    int max
    int elementsAboveMax = 1
}

push {
    if (stack.peek.max < val)
    	stack.push( StackNode(val) )
    else
        stack.peek.elementsAboveMax++
}

pop {
    if (--stack.peek.elementsAboveMax == 0) stack.pop()
}

print {
    sout( stack.peek.max )
}

Nice work. Clean

Genious

Wish I'd thought of it!

one thing is that, each node holds one more information about the max value.

Solution for python 3

class Stack(): def init(self): self.items=[] def size(self): return len(self.items) def isEmpty(self): return self.items==[] def pop(self): return self.items.pop() def push(self,item): self.items.append(item) def peek(self): return self.items[len(self.items)-1]

N=int(input()) s1=Stack() curMax=Stack() for i in range(N): query=list(map(int,input().split())) if(query[0]==1): cur=query[1] if(curMax.isEmpty() !=True) : if(curMax.peek()<=cur): curMax.push(cur) else: curMax.push(cur) s1.push(cur) elif(query[0]==2): if((s1.isEmpty() and s1.isEmpty()) != True): if(s1.peek()==curMax.peek()): curMax.pop() s1.pop() elif(query[0]==3): print(curMax.peek())

I tried your code and it's taking slightlty more time on Netbeans. Here's mine btw

public class Solution {

public static void main(String[] args) {

    Scanner inp = new Scanner(System.in);
    int n = inp.nextInt();
    Stack<Integer> S = new Stack<>();
    Stack<Integer> largest_stack = new Stack<>();
    largest_stack.push(0);

    for(int i=1; i<=n;i++){
        int query = inp.nextInt();

        if(query==1){
            int newtop=inp.nextInt();
            S.push(newtop);

            if(S.peek()>=largest_stack.peek()){
                largest_stack.push(S.peek());     
            }


       }

        if(query==2){
            if(S.peek()==largest_stack.peek()){
                largest_stack.pop();   
            }

            S.pop();   
        }



        if(query==3){
            System.out.println(largest_stack.peek());
        }


}
}
}

Simple and super:)

What a clean and smart solution. Solving it in O(N) is remarkable!

@dray92 , Hi, I am just wondering why set max = stack.peek().curMax when the choice ==2. I am kind of confused that part. According to the description, you just pop the top of your stack, right? Can you please explain the situation. Sorry about my stupidity.

Please explain stack.peek().curmax why has it been used? Stack.peek() returns the top of stack What does its curmax return? I am new to programming. Your help will be highly appreciated.

Why is the toString function needed here? Also,what happens if you pop off the max value from the stack?

This is brilliant solution.

Can also implement with 1 array to minimize memory usage.

Awesome idea!!!

Very clever

Hi Dary, Is your code outperfoming mine in space complexity? I am taking an arraylist[element,maxSeenUntilNow] as a stack element?

import java.io.; import java.util.;

public class Solution { static Stack stack= new Stack();

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    Scanner sc= new Scanner(System.in);
    //   Scanner in = new Scanner(System.in);
    //float T = Float.parseFloat(in.nextLine());
    //int N = Integer.parseInt(in.nextLine());

    while(sc.hasNextLine()){
        stackOperations(sc.nextLine());
    }
}
   public static void stackOperations(String line){

    if ((line.split(" ").length)==2){
        Integer to_be_pushed=Integer.parseInt(line.split(" ")[1]);
        //System.out.println(to_be_pushed);
        List newArrayList= new ArrayList();
        int maxVal;
        if (!stack.isEmpty()){
            ArrayList  newal=(ArrayList)stack.peek();
            maxVal = (to_be_pushed > (Integer)newal.get(1)? to_be_pushed :  (Integer) newal.get(1));
        }else {
            maxVal=to_be_pushed;
        }
        newArrayList.add(to_be_pushed);
        newArrayList.add(maxVal);

        stack.push(newArrayList);
    }
    else{
        //2    -Delete the element present at the top of the stack.
        //3    -Print the maximum element in the stack.
        if (Integer.parseInt(line.split("")[0])==2){
            if  (stack.size()!=0){
                stack.pop();
            }
        }
        else if (Integer.parseInt(line.split(" ")[0])==3){
            ArrayList peeklist= (ArrayList)stack.peek();
            System.out.println((Integer)peeklist.get(1));
        }

    }
}

}

great bro..

I think for this task creation of additional class is needless. You could just store max int value at the stack during push, since we anyway don't use stack values other than getting the max. Thus, with every push the top of the stack will contain max element, popping element will bring you to the previous max element.

Nice solution. But how is this O(n)? It depends upon the input size n.

Here's my version of solution for this problem.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> maxStack = new Stack<Integer>();
        
        while (n > 0) {
            int choice = sc.nextInt();
            if (choice == 1) {
                Integer val = sc.nextInt();
                if (val >= getStackMax(maxStack))
	                maxStack.push(val);
                stack.push(val);
            } else if (choice == 2) {
                Integer value = stack.pop();
                if (value == getStackMax(maxStack))
                	maxStack.pop();
            } else if (choice == 3) {
                if (!maxStack.isEmpty()) {
	                System.out.println(getStackMax(maxStack));
                }
            }
            n--;
        }
	    sc.close();
    }
	
    private static Integer getStackMax(Stack<Integer> s) {
        if (s.isEmpty()) 
            return Integer.MIN_VALUE;
        return s.peek();
    }
}

Good one

nice dude

A little late -- but I'm wondering why can't for choice== 3 statement we can't just print out the max variable we instantiated in the main method.

How about we just store the maximum values?

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static class StackNode{
        int val;
        StackNode(int val){
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Stack<StackNode> myStack = new Stack<>();
        while(n-->0){
            int type = in.nextInt();
            if(type==1){
                int x = in.nextInt();
                myStack.push(new StackNode(myStack.empty()?x:Math.max(x, myStack.peek().val)));
            }
            else if(type==2)
                myStack.pop();
            else
                System.out.println(myStack.peek().val);
        }
    }
}

Its taking O(n) space to keep track of current Max Element(not O(1)).

Slightly simplified version:

    static Scanner in = new Scanner( System.in );
    static Deque<Integer> stack = new ArrayDeque();
    static Integer max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        int numQueries = in.nextInt();

        for ( int i=0; i<numQueries; i++ )
            switch( in.nextInt() ) {
                case 1: 
                    int n = in.nextInt();
                    max = Math.max( n, max );
                    stack.push( max );
                    break;
                case 2:
                    stack.pollFirst();
                    if ( stack.isEmpty() )
                        max = Integer.MIN_VALUE;
                    else
                        max = stack.peek();
                    break;
                case 3: System.out.println( max ); break;
            }
    }
}

c++ solution. Passed all tests:

int main() {
    int N;
    cin >> N;
    
    vector <int> s;
    vector <int> max;
    max.push_back(0);
    while (N--) {
        int q;
        cin >> q;
        
        if (q==1) {
            int x;
            cin >> x;
            s.push_back(x);
            if ((x>=max.back())) max.push_back(x);
        }
        else if (q==2) {
            if (s.back()==max.back()) max.pop_back();
            s.pop_back();
        }    
        else cout << max.back() << endl;
    }

    return 0;
}

Javascript version:

class StackNode{
    constructor(value,currentStackMax){
        this.value = value;
        this.currentStackMax = currentStackMax;
    }
}
function processData(input) {
    //Enter your code here

    const inputs = input.split('\n');
    const numberOfQuery = Number(inputs[0]);
    const MIN_MAX = 0 ;
    let currentStackMax = MIN_MAX;
    let stack = [];
    for(let i = 1;i <= numberOfQuery;i++){
        const query = inputs[i];
        const type = Number(query.split(' ')[0]);
        const value = Number(query.split(' ')[1]);
    
        switch(type){
            case 1:
          
                currentStackMax = Math.max(value,currentStackMax);
            
                stack.push(new StackNode(value,currentStackMax));
            break;
            case 2:
                let popNum = stack.pop();
                if(stack.length==0){
                   currentStackMax = MIN_MAX;
                }else{
                   currentStackMax = stack[stack.length-1].currentStackMax;                    
                }

                
            break;
            case 3:
                console.log(stack[stack.length-1].currentStackMax);
            break;
            default:
               console.log('unknown type',type); 
               
                
        }
   
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Yup but O(n) durint a pop

No point of using toString method if you are calling System.out.println(stack.peek().curMax); for case 3; if you really want to make use of the to string method then a bit of modification is needed.

public String toString() {
        return curMax + "";
    }

now call System.out.println(stack.peek()); for case 3.

sacrifice space to performance.

Great Work Man !!

Can Someone help me here , In the solution, StackNode is used but does it takes auxiliary space ? I mean what is the space complexity ? is it O(1) ?

great work

what does your st.push(max(x, st.top())); do could you explain ??

Good idea!

This solution is wrong as a C\C++ solution. I am not sure how it passes all test. You need 2 stacks for this.

Algorithm is explained here: http://algorithms.tutorialhorizon.com/track-the-maximum-element-in-a-stack/

Here is my solution which is mapped off of the website provided above and it passes all test cases. The website is very good visual example:

auto query_type = 0; auto n = 0; int insert_element = 0; int max_index = 0; int max_element = 0;

stack<int> stack_list;
stack<int> max_list;

cin >> n;

for( auto i = 0; i < n;i++ )
{
    cin >> query_type;

    switch(query_type)
    {
        case 1:
            cin >> insert_element;
            if(stack_list.empty())
            {
                stack_list.push(insert_element);
                max_list.push(insert_element);
            }
            else{
                if(insert_element > max_list.top())
                {
                    max_list.push(insert_element);
                }else
                {
                    max_list.push(max_list.top());
                }
                stack_list.push(insert_element);
            }
            break;
        case 2:
            if(!stack_list.empty())
            {
                stack_list.pop();
                max_list.pop();
            }

            break;
        case 3:
            cout << max_list.top() << "\n";
        default:
            break;
    }
}

brilliant!

hey above code is showing this error - "expected expression before ‘:’ token" above std::stack st; line. can anyone explain me how can i fix it.

For the test case:
3
1 2 --> [2]
1 1 --> [2,2]
2 --> [2]
3 --> (it will display 2, but it should have displayed 1)
This solution passes all the test cases, but how is it working ? I mean, is that anything that i am not getting?

st.push(max(x, st.top()));

Ingenious!

But, isn't this solution actually changing the original stack. Shouldn't the integrity of stack be preserved for further uses in general. I feel its not a good practice to solve problem like this. Please tell me if I am going wrong way;

Your logic is great Really Impressive

Have you tried it against HackerRank engine? What's the slowest time using this solution?

Nice!

The algo should take care of the fact that once an element is popped, the new stack can have a new maximum value. so the next print should print the new max value. If we simply push max(x, top_of_stack), all values lower than top_of_stack will be ignored (same max is pushed again) and after a pop, the stack will not have a new max.

Thanks for clarifying that. Very clever and much faster, wow.

It looks like you just hack it. Because your stack will be different from, I mean, the true stack that we need. Suppose that if in the test cases, they check the value that you just pop out in query 2, so you will fail. But it's not important anymore, you passed the test cases by a hacker-style way, and I like it.

Great..!!!

Here's a C++ implementation of the logic that Josh_ gave, passes all the test cases.

int main() {

    stack<int> myStack;

    int n, q, max = 0, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> q;

        if (q == 1) {
            cin >> x;
            if (x > max) {
                myStack.push(x);
                max = x;
            }
            else
                myStack.push(max);
        }
        else if (q == 2) {
            myStack.pop();
            if (myStack.empty())
                max = 0;
            else if (myStack.top() != max)
                max = myStack.top();
        }
        else if (q == 3) {
            cout << myStack.top() << endl;
        }
    }
    return 0;
}

Thanks man

Nice solution!

I'm wondering why you have to compare the input with the last item in the items list to get the maximum before yiu append it. Is it stated somewhere in the question? or is it implied in the tests?

This works because we don't care about poped elements. We only care about the max :)

this wouldn't work if the input sequence has negative integers right?

nice !!! there is no really need of a 2nd stack, we're only dealing with this max query

What does this do : s.push(max(k, s.size()>0?s.top():k))

This is the coolest solution I have seen for this sum till now. Thanks @jcfxcode :)

Your solution worked and thank you for that. But how did it happen?

hey that worked thankyou

yes I got the same problem. can you explain why?

I am not sure why, but yes running the code in Java 8 solves those failures related to timeout.

yes, use java 8 instead of 7.....

That info saved my time :P

This is genius. Very beautiful.

While I have problem with various of these (one of them rather notorious, but still +11 in the voting), this one seemed straightforward). Take the example given:

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

10 lines of input

• 1 97: push 97 on the stack
• 2: pop the top element (97) from the stack (leaving an empty stack)
• 1 20: push 20 on the stack
• 2: pop the top element (20) from the stack (leaving an empty stack)
• 1 26: push 26 on the stack
• 1 20: push 20 on the stack (now 26, 20)
• 2: pop the top element (20) from the stack (leaving 26 on the stack)
• 3: print the max element (26)
• 1 91: push 91 on the tack (now 26, 91)
• 3: print the max element (91)

Beware of cases where a number identical to the current max is pushed (e.g., 21, 91, 26, 91, 20)

The heart of the problem: can you write an efficient (or relatively efficient) algorithm to find the maximum element on the stack, regardless of stack size?