Maximum Element Hackerrank problem solution

Maximum Element Hackerrank

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x -Push the element x into the stack.
2 -Delete the element present at the top of the stack.
3 -Print the maximum element in the stack.

Input Format

The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

Constraints
1<=N<=105
1<=x<=109
1<=type<=3
Output Format

For each type 3 query, print the maximum element in the stack on a new line.

Sample Input

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

Sample Output

26
91

Solution

The approach is pretty straight forward. We keep two stacks: One is for pushing and popping elements as they come and go (elements stack), and the other is for keeping track of the maximum element (maximum elements stack).

When the first element arrives, push it onto both of the stacks. As the elements may not be distinct, we need to keep track of their indices. So, declare a stack of pair or use a structure.

We maintain the maximum elements stack so that the maximum element till now is on the top. Whenever we push an element, it normally goes to the elements stack, but we also push it to the maximum elements stack if, and only if, it is greater than the current maximum element.

Now, when an element is to be deleted, we pop it directly from the elements stack. We also check if that particular element is the maximum element or not. We do so by comparing the value and the index of the popped element with the element on top of the maximum elements stack. If they are equal, we pop that element as well.

Finally, to answer the maximum element query 3, we print the element on top of the maximum elements stack.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    stack <int> s;
    int n,x,t;
    cin>>n;
    while(n--){    
        cin>>t;
        if(t==1){
            cin>>x;
            if(s.empty())
              s.push(x);
             else
              s.push(max(x,s.top()));
        }
        else if(t==2){
                 if (!s.empty())
                     s.pop();
        }
         if(t==3){
             cout<<s.top()<<endl;
              
        }
            
    }
    return 0;
}
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class maximumElement3 {

    public static void main(String[] args) {
	//File file = new File("./testmaximumElement5.txt");
	try {
	    Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();

	    Stack<Integer> st = new Stack<Integer>();
	    int max = 0;
	    int max_count = 0;

	    for (int i = 0; i < n ; i++) {
		int j = 0;
		try {
		    j = sc.nextInt();
		} catch (Exception ee) {
		    System.out.println(max);
		    continue;
		}
		int k = 0;
		if (j == 1) {
		    k = sc.nextInt();
		    st.push(k);
		    if (k > max) {
			max = k;
			max_count = 1;
		    } else if (k == max) {
			max_count++;
		    }

		} else if (j == 2) {
		    if (!(st.isEmpty())){
			    k = st.pop();
			    if (k == max) {
				max_count--;
				if (max_count == 0) {
				    max =  0;
				    Iterator iter = st.iterator();
				    while (iter.hasNext()) {
					int temp = (Integer) iter.next();
					if (temp > max ) {
					    max = temp;
					    max_count = 1;
					} else if (temp == max) {
					    max_count++;
					}
				    }
				}
			    }
		    }
		} else if (j == 3) {
		    if (max != 0) System.out.println(max);
		}
	    }
	} catch (Exception e) {
	    e.printStackTrace();
	}

    }
}
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    stack <int> s;
    int n,x,t;
    cin>>n;
    while(n--){    
        cin>>t;
        switch(t){
            case 1:
                cin>>x;
                if(s.empty())
                    s.push(x);
                else
                    s.push(max(x,s.top()));
                 break;
            case 2:
                 if (!s.empty())
                     s.pop();
                break;
            case 3:
                cout<<s.top()<<endl;
                break;
            default:
                break;
        }
            
    }
    return 0;
}
import heapq 
def MM2(N):
    m = []
    A1 = None #Type of Command 
    A2 = None #Number to be Pushed to Stack
    m2 = []
    for i in range(N):
        try:
            inn = raw_input()
        except:
            inn = inn 
        if len(inn) > 1:
            A1 = int(inn.split()[0])
            A2 = int(inn.split()[1])
        else:
            A1 = int(inn)
        if A1 == 1:
            m.append(A2) # pushing to stack
            heapq.heappush(m2,-A2) # pushing to Priority Queue (the - to get the greatest value)
        if A1 == 2:
            A2 = m.pop()
            if A2 == -m2[0]:# if value to be popped from stack is the largest value remove it from PQ
                 heapq.heappop(m2)
            else:
                m2.remove(-A2)
                heapq.heapify(m2)
        if A1 == 3:
            #pass
            print(-m2[0])
        #print (m2)
 
        
N = int(raw_input())
MM2(N)
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;

int main()
{
    stack<pair<int,int> > ele, maxi;
    int n, i = 1;
    cin>>n;
    while(i <= n)
    {
        int t, v;
        pair<int, int> p1, p2;
        cin>>t;
        if(t == 1)
        {
            cin>>v;
            ele.push(make_pair(v, i));
            if(maxi.size() == 0)
            {
                maxi.push(make_pair(v, i));
            }
            else
            {
                p1 = maxi.top();
                if(p1.first < v)
                {
                    maxi.push(make_pair(v, i));
                }
            }
        }
        else if(t == 2)
        {
            p1 = ele.top();
            ele.pop();
            p2 = maxi.top();
            if(p1.first == p2.first && p1.second == p2.second)
            {
                maxi.pop();
            }
        }
        else
        {
            p1 = maxi.top();
            cout<<p1.first<<endl;
        }
        i++;
    }
    return 0;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.