We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Maximum Element
  5. Discussions

Maximum Element

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 1358 Discussions, By:

votes

Please Login in order to post a comment

  • dray92
    6 years ago+ 56 comments

    Posting a Java solution, that has O(1) access to get the maximum value in the stack.

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = Integer.MIN_VALUE;
        Stack<StackNode> stack = new Stack<StackNode>();
    
        while (n > 0) {
            int choice = sc.nextInt();
            if(choice == 1) {
                int val = sc.nextInt();
                max = Math.max(val, max);
    
                stack.add(new StackNode(val, max));
            } else if(choice == 2) {
                if(!stack.isEmpty())
                    stack.pop();
                // reset max
                if(stack.isEmpty())
                    max = Integer.MIN_VALUE;
                else
                    max = stack.peek().curMax;
            } else if(choice == 3) {
                if(!stack.isEmpty()) {
                    System.out.println(stack.peek().curMax);
                }
            }
    
            n--;
        }
        sc.close();
    }
    
    private static class StackNode {
        int val;
        int curMax;
        public StackNode(int val, int curMax) {
            this.val = val;
            this.curMax = curMax;
        }
    
        public String toString() {
            return val + " [" + curMax + "]";
        }
    }
    
    199|
    Permalink
    View more Comments..
  • haruelrovix
    6 years ago+ 23 comments

    Solution using C++, the slowest time is 0.02s

    int main() {
        std::stack<int> st;
        int n, x;
        scanf("%d", &n);
    
        for (int i = 0; i < n; i++) {
            int q;
            scanf("%d", &q);
    
            switch (q)
            {
            case 1:
                scanf("%d", &x);
    
                if (st.empty()) {
                    st.push(x);
                }
                else {
                    st.push(max(x, st.top()));
                }
                break;
    
            case 2:
                if (!st.empty()) {
                    st.pop();
                }
                break;
    
            case 3:
                printf("%d\n", st.top());
                break;
    
            default:
                break;
            }
        }
    
        return 0;
    }
    
    93|
    Permalink
    View more Comments..
  • RaoPisay
    5 years ago+ 18 comments

    Short and simple without custom stack implemenatation.

    #python 3
    items = [0]
    for i in range(int(input())):
        nums = list(map(int, input().split()))
        if nums[0] == 1:
            items.append(max(nums[1], items[-1]))
        elif nums[0] == 2:
            items.pop()
        else:
            print(items[-1])
    
    83|
    Permalink
    View more Comments..
  • Josh_
    6 years ago+ 9 comments

    [Solution Spoilers]

    It seems the editorial solution and several mentioned here are needlessly complex. We do not need to maintain two stacks. Instead, we can use a single stack of integers: For query (1), instead of pushing element X, we simply push max(x, stack.peek()). For query (2), simply pop an element. For query (3), print stack.peek().

    In a nutshell, we don't care that X is at the top of the stack if there is an element Y > X further down in the stack, so why not just push Y?

    28|
    Permalink
    View more Comments..
  • cakerusk
    5 years ago+ 4 comments

    For this particular question, we can simply keep a stack of the maximum values only at every level and ignore the original data of the stack.

    Java O(1) solution :

    public class Solution {
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int queries = in.nextInt();
            Stack<Integer> maxValues = new Stack<Integer>();
            
            while(queries-- > 0) {
             switch(in.nextInt()) {
              case 1 : int item = in.nextInt();
                	   if (!maxValues.isEmpty()) {
                         item = item > maxValues.peek() ? item : maxValues.peek();
                       }
            	   maxValues.push(item);
                       break;
              case 2 : maxValues.pop();
                       break;
              case 3 : System.out.println(maxValues.peek());
                       break;
    	 }
            }
            
            in.close();
        }
    }
    
    22|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature