0

Hey guys i have some data structure challenges that i really don't know how to solve better.

I had a correct solution but the time exceed some limit, the code should follow N instructions:

  • add X number to a stack when I type 1
  • delete the top of the stack with 2
  • and print the max number in the stack with 3

that way

It it suposed to be solved with arrays, arraylists, stack, queues or trees. That is what I did, but it exceed 6.51 s:

import java.util.*;

class Main {

public static void maxStack(int a, int val, Stack stack) {

    switch (a) {
        case 1:
            stack.add(val);
            break;
        case 2:
            if (stack.isEmpty()) {
                break;
            }
            int c = (int) stack.pop();
            break;
        case 3:

            Object o[] = stack.toArray();
            Arrays.sort(o);
            System.out.println(o[o.length - 1]);
            break;
        default:
            break;
    }
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    Stack<Integer> stack = new Stack<Integer>();

    int val = 0;

    int a = scan.nextInt();
    while (a-- > 0) {
        int t = scan.nextInt();
        if (t == 1) {
            val = scan.nextInt();
        }
        maxStack(t, val, stack);
    }
    scan.close();
}
}

Any recommendation?

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
Javier Mauricio Pinilla Garcia
  • 1
  • 1
  • Warning: you are using raw types, i.e. `Stack` instead of `Stack`. Using raw types is only allowed for backward-compatibility, and should not be written in new code. – MC Emperor Oct 15 '18 at 18:38
  • Then maybe you need a better way to keep track of the maximum item on the stack. I suggest you study https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/, but rather than keeping track of the smallest item, you keep track of the largest. – Jim Mischel Oct 15 '18 at 23:13

1 Answers1

0

You are exceeding the time because each time you're performing the sort operation on them. This problem can be solved in two ways

  1. using O(1) time and O(n) space using an auxiliary stack
  2. using O(1) time and O(1) space

insert, delete, max in O(1)

suvojit_007
  • 1,690
  • 2
  • 17
  • 23