Hackerrank Sparse Arrays Solution in Java

Question

I've just solved this problem and I hope you guys give me any feedback to make my code be better.

Problem: There are N strings. Each string's length is no more than 20 characters. There are also Q queries. For each query, you are given a string, and you need to find out how many times this string occurred previously.

Input Format

The first line contains N, the number of strings. The next N lines each contain a string. The N + 2nd line contains Q, the number of queries. The following Q lines each contain a query string.

import java.io.*;
import java.util.*;

public class Solution {

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

        for (int i = 0; i < n; i++){
                stringArr[i] = scan.next();              
            }

        int q = scan.nextInt();
        for (int i = 0; i < q; i++){
                String stringQue = scan.next();

                int occNum = 0;
                for (int j = 0; j < n; j++){
                    if (stringQue.equals(stringArr[j])) occNum++;                                           
                }
             System.out.println(occNum);
        }   
    }
}

Answer 1

        String[] stringArr = new String[n];

        for (int i = 0; i < n; i++){
                stringArr[i] = scan.next();              
            }

Why use an array? Consider

        Map<String, Integer> inputCounts = new HashMap<>(n);

        for (int i = 0; i < n; i++) {
            String input = scan.next();

            Integer count = inputCounts.get(input);
            if (count == null) {
                count = 0;
            }

            count++;
            inputCounts.put(input, count);
        }

Now you know the count for each input string. So

                String stringQue = scan.next();

                int occNum = 0;
                for (int j = 0; j < n; j++){
                    if (stringQue.equals(stringArr[j])) occNum++;
                }
             System.out.println(occNum);

could become just

                String query = scan.next();

                Integer count = inputCounts.get(query);
                if (count == null) {
                    count = 0;
                }                          

                System.out.println(count);

If the overhead of the hash accesses is less than the overhead of the for loop, this might be faster.

A HashMap converts the string key into a location in the Map. This is more expensive than a numeric array selection but is probably similar to the cost of the equals method.

I think that we can safely say that accessing the HashMap is going to be faster than iterating over every member of the array unless the array is tiny. The larger question is if the cost of building the HashMap is going to be greater than the savings in processing the queries. For a large number of strings and a small number of queries, the cost of building the HashMap can outweigh the savings in processing the queries. That's trivially true if there are zero queries. And may still be true for one query. There is some point where it stops being true. You'd have to benchmark to be sure.

I prefer names like query and count to stringQue and occNum.