Phone number duplication detector

Question

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<String, Integer> dict = new TreeMap<String, Integer>();
    
    for(int i = 0; i < 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) > 1) {
            hasDuplication = false;
            System.out.println(number + " " + dict.get(number));
        }
    }
    if(hasDuplication) {
        System.out.println("No duplicates.");
    }
}

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

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

}

Answer 1

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<String, Integer> dict = new TreeMap<String, Integer>();

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<String, Integer> dict = new HashMap<>();

This should perform faster for larger inputs.

Pick the right method

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

This is the use case for an entrySet.

    for (Map.Entry<String, Integer> entry : dict.entrySet()) {
        if (entry.getValue() > 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 < 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.

Answer 2

Use a profiler to measure where the time is spent!

That said, your convert method is very inefficient. It uses multiple string operations. You can make it one-pass using the characters as they come by.

We need some extra cases to be able to prevent upper/lowercasing.

public static String toBaseForm(String raw) {
        StringBuilder sb = new StringBuilder();
        for (char ch : raw.toCharArray()) {
            if (ch >= 'A' && ch < 'Q') {
                sb.append((char) ((ch - 'A') / 3 + '2'));
            } else if (ch >= 'Q' && ch < 'Z') {
                sb.append((char) ((ch - 'Q') / 3 + '7'));
            } else if (ch >= 'a' && ch < 'q') {
                sb.append((char) ((ch - 'a') / 3 + '2'));
            } else if (ch >= 'q' && ch < 'z') {
                sb.append((char) ((ch - 'q') / 3 + '7'));
            } else if (ch >= '0' && ch <= '9') {
                sb.append(ch);
            }
            if (sb.length() == 3) {
                sb.append('-');
            }
        }
        return sb.toString();
    }

Answer 3

String allocations

You make a number of allocations that may not be obvious:

public static String convert(String raw) {
    raw = raw.replaceAll("-", ""); // possibly new string, if contains hyphen
    raw = raw.toLowerCase(); // possibly new string, if contains uppercase
    String number = "";
    for(int i = 0; i < raw.length(); i++) {
        number += parse(raw.charAt(i)); // definitely new string, raw.length() times!
    }
    number = number.substring(0, 3) + "-" + number.substring(3); // three new strings: sub + sub + result
    return number;
}

String is immutable in Java, meaning any operations that result in different char data will result in a different string. String.substring also (usually) creates a new string.

The input "888-GLOP" ends up creating eleven new strings before returning its final, twelfth string!

Map.get + Map.put = Map.merge

if(!dict.containsKey(numbers[i])) { // Θ(log n)
    dict.put(numbers[i], 1); // Θ(log n)
} else {
    dict.put(numbers[i], dict.get(numbers[i]) + 1); // Θ(log n) + Θ(log n)
}

// -->

dict.merge(numbers[i], 1, Integer::sum);

Still, you are sorting/comparing strings each time you want to update your map. You could split into two parts: one part that checks whether you have already seen the input before (doesn't need to be sorted), and another that keeps track of your actual duplicates:

HashSet<String> seen;
TreeMap<String, Integer> duplicates;

// Set.add returns false if already contained
if ( !seen.add(number) ) { // Θ(1)
  duplicates.merge(number, 1, Integer::sum); // Θ(log n)
}

// printing later -- don't forget to add 1 to dupe count!
duplicates.forEach( (k,v) -> System.out.println( ... (v + 1) ... ); )

Alternatively, you can turn the data around:

HashMap<String, Integer> frequency;
TreeSet<String> duplicates;

if ( frequency.merge(number, 1, Integer::sum) > 1 ) { // Θ(1)
  duplicates.add(number); // Θ(log n)
}

duplicates.forEach( k -> System.out.println( ... frequency.get(k) ... ); )

---

Alternative implementation

Consider that:

1. Phone numbers have a normal form, which is NNN-NNNN, with N being a digit. This makes phone numbers contain 7 digits worth of information. That fits in an int. → Less memory usage, better cache usage.

2. You don't need to retain the original form. → We can use destructive methods.

3. Your incoming alphabet is limited: uppercase letters, decimal digits, and the hyphen. → switch-case and/or table parsing are viable.

4. You need to output only the duplicates. → We don't need to store everything, but we might end up having to.

5. You need to output the duplicates in lexicographical order. → We don't need to keep everything sorted; only the duplicates.

Leading to:

import java.util.*;

public class Main {
  public static void main(String[] args) {
    final Scanner in = new Scanner(System.in);
    int count = in.nextInt();

    /* We split duplicate detection in an unsorted part that just saves whether
     * we've seen it before, and a sorted part that stores actual duplicates in
     * lexicographical order. */
    final Set<Integer> seen = new HashSet<>();
    final NavigableMap<Integer, Integer> duplicates = new TreeMap<>();

    while ( count-- > 0 ) {
      String strnum = in.next();
      final Integer number = parse(strnum);

      if ( !seen.add(number) ) {
        // number of dupes is number of encounters minus one
        duplicates.merge(number, 1, Integer::sum);
      }
    }

    if ( duplicates.isEmpty() ) {
      System.out.println("No duplicates.");
    } else {
      for ( Map.Entry<Integer, Integer> duplicate : duplicates.entrySet() ) {
        // don't forget to add one to the dupe count to get total count
        System.out.println(format(duplicate.getKey()) + " " + (duplicate.getValue() + 1));
      }
    }
  }

  /** Formats a parsed phone number to its normal form (NNN-NNNN). */
  static String format(int phoneNumber) {
    final int prefix = phoneNumber / 10000;
    final int suffix = phoneNumber % 10000;
    return String.format("%03d-%04d", prefix, suffix);
  }

  /** Parses an unformatted phone number string, considering only the alphanumerics.
    * Does not guard for overflow. */
  static int parse(String number) {
    int retval = 0;
    for ( int i = 0; i < number.length(); i++ ) {
      int digit;
      final char c = number.charAt(i);
      switch ( c ) {
        case '0':
          digit = 0;
          break;

        case '1':
          digit = 1;
          break;

        case '2': case 'A': case 'B': case 'C':
          digit = 2;
          break;

        case '3': case 'D': case 'E': case 'F':
          digit = 3;
          break;

        case '4': case 'G': case 'H': case 'I':
          digit = 4;
          break;

        case '5': case 'J': case 'K': case 'L':
          digit = 5;
          break;

        case '6': case 'M': case 'N': case 'O':
          digit = 6;
          break;

        case '7': case 'P': case 'R': case 'S':
          digit = 7;
          break;

        case '8': case 'T': case 'U': case 'V':
          digit = 8;
          break;

        case '9': case 'W': case 'X': case 'Y':
          digit = 9;
          break;

        default:
          continue;
      }

      retval = 10 * retval + digit;
    }

    return retval;
  }
}