How to increase performance on manipulating large arrays?

Question

I am solving a problem on Hackerrank right now and I believe my logic is more or less correct, but the larger datasets are slowing down the performance so as to give me a "wrong" answer. Here is a link to the problem so you can check it out:

https://www.hackerrank.com/challenges/qheap1

I am wondering how to increase the performance of this script so as to allow for larger datasets. I have a hunch it has to do with the Scanner, but I don't know why.

public class Solution {
    private static final int ADD = 1;
    private static final int DELETE = 2;
    private static final int GET = 3;
    private static final int TICK = 1;
    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 in = new Scanner(System.in);
        PrintStream out = System.out;
        int n = in.nextInt();
        int[] heap = new int[n];

        int a = 0;
        while (a < n) {
            a = 0;
            int q = in.nextInt();

            switch(q) {
                case(ADD):
                    int nextAdd = in.nextInt();
                    /*out.println("ADD " + next);*/
                    int b = 0;
                    while (b < n) {
                        /*out.println(heap[b]);*/
                        if (heap[b] == 0) {
                            heap[b] = nextAdd+TICK;
                            /*printArray(heap);*/
                            b = n-1;
                        }
                        b++;
                    }
                    /*printArray(heap);*/
                    break;
                case(DELETE):
                    int c = 0;
                    int nextDelete = in.nextInt();
                    while (c < n) {
                        if (heap[c]-TICK == nextDelete) {
                            heap[c] = 0;
                            c = n-1;
                        }
                        c++;
                    }
                    /*printArray(heap);*/
                    break;
                case(GET):  
                    Arrays.sort(heap);
                    int d = 0;
                    while (d < n) {
                        if (heap[d] != 0) {
                            out.println(heap[d]-TICK);
                            d = n-1;
                        }
                        d++;
                    }
                    /*printArray(heap);*/
                    break;
            }
            a++;
            /*printArray(heap);*/
        }
    }

    public static void printArray(int[] ar) {
        String str = "";
        for (int i : ar) {
            str += i + " ";
        }
        System.out.println(str);
    }
}

Answer 1

The main problem with your approach that you don't use heap (as it is required by challenge), you're spending too much time working with array.

Here is the implementation which passes all tests:

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

    final int n = in.nextInt();
    final PriorityQueue<Integer> q = new PriorityQueue<>(n);
    for (int i = 0; i < n; i++) {
        final int command = in.nextInt();
        switch (command) {
        case 1:
            q.add(in.nextInt());
            break;
        case 2:
            q.remove(in.nextInt());
            break;
        case 3:
            System.out.println(q.peek());
            break;
        }
    }
}

Answer 2

Looking at your code, the only immediate problem that I can spot is the fact that this line

out.println(heap[d]-TICK);

isn't commented out. That could mean that your java program (no, it is not a script, mind your wording!) is doing a lot of IO operations. And those are very expensive compared to anything else going on in your program.

So, comment that out and see what happens then.