Phone number duplication detector I am doing the POJ 1002 question. My code works fine but the website says the compilation time is more than 2000ms, which is not accepted. How can I improve my time-wise performance?
Problem Statement

Input — The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be digits or letters.
Output — Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line:
No duplicates.

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main{

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int total = scan.nextInt();
    scan.nextLine();                // But why?
    String[] numbers = new String[total];
    Map&lt;String, Integer&gt; dict = new TreeMap&lt;String, Integer&gt;();
    
    for(int i = 0; i &lt; total; i++) {
        numbers[i] = scan.nextLine();
        numbers[i] = convert(numbers[i]);
        if(!dict.containsKey(numbers[i])) {
            dict.put(numbers[i], 1);
        } else {
            dict.put(numbers[i], dict.get(numbers[i]) + 1);
        }
    }
    
    scan.close();
    
    boolean hasDuplication = true;        
    for(String number: dict.keySet()) {
        if(dict.get(number) &gt; 1) {
            hasDuplication = false;
            System.out.println(number + &quot; &quot; + dict.get(number));
        }
    }
    if(hasDuplication) {
        System.out.println(&quot;No duplicates.&quot;);
    }
}

public static String convert(String raw) {
    raw = raw.replaceAll(&quot;-&quot;, &quot;&quot;);
    raw = raw.toLowerCase();
    String number = &quot;&quot;;
    for(int i = 0; i &lt; raw.length(); i++) {
        number += parse(raw.charAt(i));
    }
    number = number.substring(0, 3) + &quot;-&quot; + number.substring(3);
    return number;
}

public static char parse(char digit) {
    if(digit &gt;= 'a' &amp;&amp; digit &lt; 'q') {
        digit = (char) ((digit-'a') / 3 + '2');
    } else if(digit &gt; 'q' &amp;&amp; digit &lt; 'z') {
        digit = (char) ((digit-'q') / 3 + '7');
    }
    return digit;
}

}
Chomp the new line


    scan.nextLine();                // But why?



Nothing to do with performance, but Scanner is skipping nextLine() after using next(), nextInt() or other nextFoo()? explains this.  

Remove unnecessary data structure


    String[] numbers = new String[total];



You never use numbers as an array.  You could get rid of it entirely.  


        numbers[i] = scan.nextLine();
        numbers[i] = convert(numbers[i]);
        if(!dict.containsKey(numbers[i])) {
            dict.put(numbers[i], 1);
        } else {
            dict.put(numbers[i], dict.get(numbers[i]) + 1);
        }



Replace numbers[i] with a single String.  

        String number = convert(scan.nextLine());

        Integer count = dict.get(number);
        if (count == null) {
            count = 0;
        }
        count++;

        dict.put(number, count);


Now we don't keep an array around for nothing.  

I also changed the get/put pattern.  This saves having to do both the containsKey check and the get.  

Consider other data structures


    Map&lt;String, Integer&gt; dict = new TreeMap&lt;String, Integer&gt;();



I would expect a TreeMap to be slower than a HashMap for most applications that depend on insert and read efficiency.  This is especially so since it sorts on keys and what you want is to find all with at least value 2.  You'd need to override the comparison to get that behavior.  

You don't use the read behavior that would be helpful.  And you accept the slower writes.  

        Map&lt;String, Integer&gt; dict = new HashMap&lt;&gt;();


This should perform faster for larger inputs.  

Pick the right method


    for(String number: dict.keySet()) {
        if(dict.get(number) &gt; 1) {
            hasDuplication = false;
            System.out.println(number + " " + dict.get(number));
        }
    }



This is the use case for an entrySet.  

    for (Map.Entry&lt;String, Integer&gt; entry : dict.entrySet()) {
        if (entry.getValue() &gt; 1) {
            hasDuplication = true;
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }


Now we don't have to do an expensive get lookup operation on each iteration.  

I'd also switch the meaning of hasDuplication to match the name.  Don't forget to switch it the other two places as well.  


    boolean hasDuplication = true;



to 

    boolean hasDuplication = false;


and 


    if(hasDuplication) {



to 

    if (!hasDuplication) {


Other possibilities

If this doesn't help, consider splitting reading the input from processing it.  So something like 

    for (int i = 0; i &lt; numbers.length; i++) {
        numbers[i] = scan.nextLine();
    }

    scan.close();

    for (String number : numbers) {
        number = convert(number);

        Integer count = dict.get(number);
        if (count == null) {
            count = 0;
        }
        count++;

        dict.put(number, count);
    }


I didn't test this, so you may have to declare a new variable rather than reusing number.