Time limit exceeded even with best approach(Java)

Question

Even if I think that I solved a competitive programming problem from HackerEarth with the best approach, all tests exceed the time limit. I really do not know how to optimize it further because it is just an easy exercise.

My approach: iterate over all array members than add them to a HashMap which stores their occurrences. After that simply read the query numbers and get their occurence from the HashMap.

This is my solution:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class TestClass {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        //go through all test cases
        for (int i = 0; i < t; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            String[] inputs = br.readLine().split(" ");
            int N = Integer.parseInt(inputs[0]);
            int Q = Integer.parseInt(inputs[1]);
            inputs = br.readLine().split(" ");

            //read array
            for (int j = 0; j < N; j++) {
                int x = Integer.parseInt(inputs[j]);
                Integer value = map.get(x);
                //if number is already in hashmap then increment its count
                //else put it into the map with a count of 1
                if (value == null) {
                    map.put(x, 1);
                } else map.put(x, value + 1);
            }

            //iterate through the queries and get their occurences from the map
            for (int j = 0; j < Q; j++) {
                int x = Integer.parseInt(br.readLine());
                Integer value = map.get(x);
                if (value == null) {
                    System.out.println(0);
                } else System.out.println(value);
            }
        }
    }
}

My question is: what can be the problem with my approach? Why does it run out of time?

Answer 1

The problem with your approach is primarily it's use of BufferedReader, and the consequential information parsing you're preforming. Try an approach with scanner.

import java.util.*;
class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        int T = s.nextInt();       
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<T;i++)
        {
            StringBuilder sb=new StringBuilder();
            int N=s.nextInt();
            int Q=s.nextInt();
            int[] arr=new int[N];
            for(int j=0;j<N;j++)
            {
                arr[j]=s.nextInt();
                if(map.containsKey(arr[j]))
                {
                    map.put(arr[j],map.get(arr[j])+1);
                }
                else
                map.put(arr[j],1);
            }
            for(int k=0;k<Q;k++)
            {
                int X=s.nextInt();
                if(map.containsKey(X)){
                    sb.append(map.get(X)+"\n");
                }
                else{
                    sb.append(0+"\n");
                }     
            }
             System.out.println(sb.toString()); 
            map.clear();
        }

    }
}

This will remove a lot of the unnecessary parsing you are doing with:

 String[] inputs = br.readLine().split(" ");
 int N = Integer.parseInt(inputs[0]);
 int Q = Integer.parseInt(inputs[1]);
 inputs = br.readLine().split(" ");

Please look at Scanner vs. BufferedReader to understand why Scanner is situationally faster here. Essentially BufferedReader is faster in it's ability to simply read the lines, but when you use BufferedReader here, you are then forced to use Integer.parseInt(...) and br.readlines().split(" ") to parse the information you need from the input; however, scanner has built in parsing mechanisms that can read and parse the data asynchronously. As you will see, this approach passes the test in 4-8 seconds. Additionally you could benefit from using StringBuilder, and not using:

Integer value = map.get(x);
if (value == null) {
    pr.println(0);
} else pr.println(value);

With the built in method map.containsKey(x).

Scanner is used for parsing tokens from the contents of the stream while BufferedReader just reads the stream and does not do any special parsing.

In fact you can pass a BufferedReader to a scanner as the source of characters to parse.

Furthermore:

A scanner on the other hand has a lot more cheese built into it; it can do all that a BufferedReader can do and at around the same level of efficiency as well. However, in addition a Scanner can parse the underlying stream for primitive types and strings using regular expressions. It can also tokenize the underlying stream with the delimiter of your choice. It can also do forward scanning of the underlying stream disregarding the delimiter!

There is a large difference in runtime when you have to call inputs = br.readLine().split(" "); and Integer.parseInt(..) multiple times, versus simply calling s.nextInt(). You are already reading the data with br.readLine(), when you call Integer.parseInt(...) the data is read again by the parseInt() function.

Answer 2

Ok, so the problem is not so obvious. I took a look at the input files and they are huge so you have to use some really fast method for writing to the console(many test cases -->> many answers). You can use PrinteWriter for that.

Working solution:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

class TestClass {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pr = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());

        //go through all test cases
        for (int i = 0; i < t; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            String[] inputs = br.readLine().split(" ");
            int N = Integer.parseInt(inputs[0]);
            int Q = Integer.parseInt(inputs[1]);
            inputs = br.readLine().split(" ");

            //read array
            for (int j = 0; j < N; j++) {
                int x = Integer.parseInt(inputs[j]);
                Integer value = map.get(x);
                //if number is already in hashmap then increment its count
                //else put it into the map with a count of 1
                if (value == null) {
                    map.put(x, 1);
                } else map.put(x, value + 1);
            }

            //iterate through the queries and get their occurences from the map
            for (int j = 0; j < Q; j++) {
                int x = Integer.parseInt(br.readLine());
                Integer value = map.get(x);
                if (value == null) {
                    pr.println(0);
                } else pr.println(value);
            }
        }
        pr.close();
    }
}  

Yes, I know that it is strange that the exercise itself is not so hard, but reading the input and writing the result is the big part of it.