9
\$\begingroup\$

I have been solving this problem of Hackerrank recently .. https://www.hackerrank.com/challenges/maximum-element

A little bit about the problem

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.

And my code is here - which passes the first 12 test cases.

import java.util.*;

public class Stackers {

    public static Stack<Integer> stack;
    public static String output = "";

    public static void main(String[] args) {

        stack = new Stack<>();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i = 0 ; i < n + 1; i++){

            String op = sc.nextLine();
            performOperation(op);           

        }

        sc.close();
        if(!output.isEmpty()){
            System.out.println(output);

        }

    }

    public static void performOperation(String op) {

        if (op.startsWith("1")){

            String remains = op.split(" ")[1];
            int rem = Integer.valueOf(remains);
            stack.push(rem);

        }else if(op.equalsIgnoreCase("2")){

            stack.pop();

        }else if(op.equals("3")){

            int max = (int) Collections.max(stack);
            output += (max + "\n");

        }

    }

}

But fails with "timeout" from the 13th test case. Most of the times, logic will be wrong, so I ran the 13th test case locally in my computer . I got the output in 1.3- 1.6 minutes tho:)

How can I improve my code. Please guide me or if it is the wrong stack exchange community, please advise me.

\$\endgroup\$
  • \$\begingroup\$ Just in passing, this bit looks odd (in your parser): if (op.startsWith("1")){... }else if(op.equalsIgnoreCase("2")){...}else if(op.equals("3")){...}. equalsIgnoreCase() seems very strange - were you expecting upper-case digits? ;-) It would be neater and more readable if you used the same test for all three branches, or even simply switch on the first character of op. \$\endgroup\$ – Toby Speight Mar 8 '17 at 15:38
10
\$\begingroup\$

This type of question actually requires a little thinking outside the box.

The idea here, since we need to store the max with each element, is to use the built-in Stack more creatively.

public class ChallengeValue {
    public int max;
    public int value;
}

I think that should tell you where we're going:

import java.util.*;

public class Stackers {
    public static Stack<ChallengeValue> stack;
    public static String output = "";

    public static void main(String[] args) {
        stack = new Stack<>();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i = 0 ; i < n + 1; i++){
            String op = sc.nextLine();
            performOperation(op);
        }

        sc.close();
        if(!output.isEmpty()){
            System.out.println(output);
        }
    }

    public static void performOperation(String op) {
        if (op.startsWith("1")) {
            String remains = op.split(" ")[1];
            int rem = Integer.valueOf(remains);

            ChallengeValue newVal = new ChallengeValue();
            newVal.value = rem;

            ChallengeValue last = stack.peek();
            newVal.max = last.max > newVal.value ? last.max : newVal.max;
            stack.push(newVal);
        } else if(op.equalsIgnoreCase("2")) {
            stack.pop();
        } else if(op.equals("3")) {
            int max = stack.peek().max;
            output += (max + "\n");
        }
    }
}

Now we are storing the max with the stack values, so when we pop one we get the new max immediately. This turns the max (3) command into an \$O(1)\$ operation. (Your version is likely \$O(n)\$.)

\$\endgroup\$
  • 1
    \$\begingroup\$ roflf's comment on the other answer is worth reading, for the observation that there's no need to retain value on the stack, only max. That saves a good chunk of memory usage. \$\endgroup\$ – Toby Speight Mar 8 '17 at 15:40
  • \$\begingroup\$ Also doable with two separate stacks \$\endgroup\$ – D. Ben Knoble Mar 8 '17 at 23:01
5
\$\begingroup\$

In Java, the Stack class is not a good one to use. It has been superseded by the Deque interface. The Stack class documentation has this to say: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class."

Multiple different concrete classes implement the Deque interface, and I would choose the ArrayDeque class. You can still call the variable stack.

Note that for challenges like this, it's common to skip things like input validation, and edge cases.... but you need to know that you are doing this. I would recommend leaving comments in places where you would normally have checks. Checks that you are missing are things like:

  • more pops than pushes (resulting in exceptions when popping too far)
  • values that are not valid in input (incorrect queries, non-valid integers in string format).
  • "max" on empty stacks

Further, the actual use-case in this challenge only requires that you track the maximum value at each level in the stack. You don't need to track the actual value at all. To make this easier, you can "seed" the stack with a guaranteed minimum value Integer.MIN_VALUE.

Your class has been set up using a bunch of static fields. This is not good practice. Your Stacker class should have regular fields, and your main method should create an instance of the class which has its own methods (not static methods).

The worst problem here is the output field which is a horrible way to use a static variable. In Java 8 you should consider passing in a callback function to handle output, or returning an optional in a stream. The optional is a better way....

All told, I would restructure your code to be similar to:

public class Stacker {

    private final Deque<Integer> stack = new ArrayDeque<>();

    public Optional<Integer> processOperation(String op) {
        char opc = op.charAt(0);
        switch(opc) {
        case '1':
            int previous = stack.isEmpty() ? Integer.MIN_VALUE : stack.peek();
            int max = Math.max(previous, Integer.parseInt(op.substring(1).trim()));
            stack.push(max);
            return Optional.empty();
        case '2':
            if (stack.isEmpty()) {
                throw new IllegalStateException("Cannot pop empty stack");
            }
            stack.pop();
            return Optional.empty();
        case '3':
            if (stack.isEmpty()) {
                throw new IllegalStateException("Cannot max empty stack");
            }
            return Optional.of(stack.peek());
        default:
            throw new IllegalStateException("Unknown operation:" + op);
        }
    }
}

That processOperation returns max values when the operation is a 3 op. The Optional is empty for push/pop operations.

Simpler: You can then feed instructions in to it in a loop, and collect the results of the max when the Optional has a value....

... or ....

Advanced: You can then use this in a stream of commands:

Stacker stacker = new Stacker();
String report = commands.map(stacker::processOperation)
        .filter(Optional::isPresent)
        .map(opt -> String.valueOf(opt.get()))
        .collect(Collectors.joining("\n"));

The above takes a stream of commands (commands) and runs each command through the stacker, keeping only the max results (.filter(Optional::isPresent)) and then converting those numbers to String (map(opt -> String.valueOf(opt.get()))) and then joining all those strings to a single result (.collect(Collectors.joining("\n"));).

Converting the input to a stream of string is a little fiddly, but worth it:

scanner.useDelimiter("\\s*\\n");
int count = Integer.parseInt(scanner.next());
// convert STDIN lines to a stream
Stream<String> commands = StreamSupport.stream(Spliterators.spliterator(scanner, count, Spliterator.ORDERED), false);

I ran that through the hackerranck submission and it scored 20 (full marks). The full code (using Stacker instead of Solution class name as required in hackerrank) is:

import java.io.StringReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Optional;
import java.util.Scanner;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class Stacker {

    private final Deque<Integer> stack = new ArrayDeque<>();

    public Optional<Integer> processOperation(String op) {
        char opc = op.charAt(0);
        switch(opc) {
        case '1':
            int previous = stack.isEmpty() ? Integer.MIN_VALUE : stack.peek();
            int max = Math.max(previous, Integer.parseInt(op.substring(1).trim()));
            stack.push(max);
            return Optional.empty();
        case '2':
            if (stack.isEmpty()) {
                throw new IllegalStateException("Cannot pop empty stack");
            }
            stack.pop();
            return Optional.empty();
        case '3':
            if (stack.isEmpty()) {
                throw new IllegalStateException("Cannot max empty stack");
            }
            return Optional.of(stack.peek());
        default:
            throw new IllegalStateException("Unknown operation:" + op);
        }
    }



    public static void main(String[] args) {
        String testdata = "10\n" + 
                "1 97\n" + 
                "2\n" + 
                "1 20\n" + 
                "2\n" + 
                "1 26\n" + 
                "1 20\n" + 
                "2\n" + 
                "3\n" + 
                "1 91\n" + 
                "3";

        try (Scanner scanner = new Scanner(new StringReader(testdata))) {
            scanner.useDelimiter("\\s*\\n");
            int count = Integer.parseInt(scanner.next());
            // convert STDIN lines to a stream
            Stream<String> commands = StreamSupport.stream(Spliterators.spliterator(scanner, count, Spliterator.ORDERED), false);
            // process the operations:
            Stacker stacker = new Stacker();
            String report = commands.map(stacker::processOperation)
                    .filter(Optional::isPresent)
                    .map(opt -> String.valueOf(opt.get()))
                    .collect(Collectors.joining("\n"));
            System.out.println(report);
        }
    }

}

You can see it in ideone here: https://ideone.com/1jREos

\$\endgroup\$
4
\$\begingroup\$

I suggest keeping track of the maximum element as you go along instead of using Colletions.max().

Using Collections.max() will be a big performance hit (relative to the time requirement of the problem) if the stack is extremely large, which is likely what's happening on that 13th test case.

\$\endgroup\$
  • 2
    \$\begingroup\$ Note, you don't actually need to keep track of the actual values at all, just the max. A 2-liner change from int rem = Integer.valueOf(remains); to int rem = Math.max(stack.peek(), Integer.valueOf(remains)); and a change from int max = (int) Collections.max(stack); to int max = stack.peek(); \$\endgroup\$ – rolfl Mar 8 '17 at 14:33
  • \$\begingroup\$ @rolfl, a little more than a 2-liner change since that stack.peek() will cause an error on an empty stack, but yes, that'll work. Actually I tested with those changes on Hackerrank and I'm still getting timeout errors. I think there is too much unnecessary overhead in OP's code even though the right idea is there. \$\endgroup\$ – tilper Mar 8 '17 at 14:55
  • \$\begingroup\$ Well, yeah, but that can also be solved with a simple third line, to add Integer.MIN_VALUE to the stack to start with ;-) \$\endgroup\$ – rolfl Mar 8 '17 at 15:25
  • 1
    \$\begingroup\$ @rolfl, good point, and a simpler change than I made. However, I stand by my statement on the grounds that 3 is a little more than 2. :P \$\endgroup\$ – tilper Mar 8 '17 at 15:27
2
\$\begingroup\$

In this way we can get the maximum element in O(1) time. Whenever a new element is to be inserted we just check if the stack is not empty then compare it with the top of the stack and insert the element which is greatest of the top of the stack and the element to be inserted now. In this way, the greatest element will remain at the top which we can give back in O(1) time. Otherwise, if stack is empty then simply insert the element without doing anything.

public class Solution {

public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
    Stack<Integer> stacky = new Stack<Integer>();
    int N = scan.nextInt();
    int ch;
    int x,ele=0;
    while(N-- >0){
      ch = scan.nextInt();
        if(ch==1){x = scan.nextInt();
            if(stacky.isEmpty()){
        stacky.push(x);
            }
            else{
                int y = stacky.peek();
                stacky.push(Math.max(x, y));
            }
        }

        if(ch==2){
            if(!stacky.isEmpty())
            stacky.pop();
       }

        if(ch==3){
      System.out.println(stacky.peek());
        }
    }}}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.