Sorting and eliminating duplicates

Question

From Hacker Earth:

Problem Statement:

Chotu's father is the owner of a Vada Pav shop. One Sunday, his father takes him to the shop. Father tells him that at the end of the day, Chotu has to give him a list consisting of the names of all the customers on that day who bought Vada Pav(s) from the shop. The list should not have the names of any of the customers being repeated and it should be such that the lexicographically smallest name comes first, ie., the names should be sorted in dictionary order.

As and when a particular customer buys a Vada Pav, Chotu writes down the name of that particular customer. Chotu's initial list is ready, but, he is confused as to how to make the list Father expects from him. Chotu comes to you for help. Your job now is to create the final list, as Father expects from Chotu.

Input :

First line consists of N, the number of names of customers in Chotu's initial list. The next N lines are such that each line consists of a customer's name.

Output :

On the first line, print the total number of names appearing in Chotu's final list. Then print the list such that every customer's name is printed on a new line.

Example

Sample Input:

11 
babu
anand
rani 
aarti
nandu
rani
rani
ap
anand 
babu 
nandu

Sample Output:

6
aarti
anand
ap
babu
nandu
rani

For above problem I've submitted the following code:

import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
 Scanner in = new Scanner(System.in);
 Set<String> set = new TreeSet<>();
 int n = in.nextInt();
 for(int i=0;i<n;i++){
 set.add(in.next());
 }
 System.out.println(set.size());
 Iterator i = set.iterator();
 while(i.hasNext()){
 System.out.println(i.next());
 }
}
}

But from 7 test cases, it passed 4 test cases but in rest of the test cases, the time limit exceeds. So my questions is how can I reduce time for this? I was thinking to use BufferedReader to read the whole input as a single String and than splitting it into a String array but the input is new-line separated not space separated. So I can't understand how to use fast I/O method here.

Answer 1

Why make it so complicated? Just use basic java 8 streaming operations and the new-ish BufferedReader.lines() method:

public static void main (String[] args) {
 Set<String> uniqueOrderedNames = new TreeSet<>();
 try(BufferedReader br = new BufferedReader(new InputStreamReader (System.in))){
 br.lines().forEach(uniqueOrderedNames::add);
 } catch (Exception e) {
 // don't do this, use the most specific exception type and handle it
 }
 System.out.println(uniqueOrderedNames.size());
 uniqueOrderedNames.forEach(System.out::println);
}

That much for your approach. Before you now copy paste that, I have some more things to say:

• Indent correctly: Methods are indented by one level, blocks are indented 1 level. Levels add up. Your method is missing one level of indentation and your created Scanner should be indented 2 more spaces
• Add spaces around binary operators: for(int i=0;i<n;i++){ becomes for (int i = 0; i < n; i++) {, which is significantly easier on the eyes.
• Use clear names Set set is nonsensical, it doesn't shed any light whatsoever on what the thing does. Give it a proper name so you can understand what happens.

Answer 2

I found the answer of my question myself with the help of some research. I was thinking the input is slow and that's why the time exceeds. But I was wrong: System.out.println() is comparatively slow. So I took a StringBuilder and appended the whole output strings to it and printed at last.

 Scanner in = new Scanner(System.in);
 Set<String> set = new TreeSet<>();
 int n = in.nextInt();
 for(int i=0;i<n;i++){
 set.add(in.next());
 }
 System.out.println(set.size());
 StringBuilder strb = new StringBuilder(); 
 Iterator i = set.iterator();
 while(i.hasNext()){
 strb.append(i.next()+"\n");
 }
 System.out.println(strb); 

• rdllopes: You could be right but then this programming-challenge is very odd. If writing the output was a problem, reading could also be another point to improve: stackoverflow.com/questions/7049011/…

Answer 3

You're assuming that the performance problem is due to I/O, but I find that explanation unlikely. If your code is so slow that the time limit is exceeded, it is likely that you have a problem with algorithmic complexity.

Try using a HashSet instead for fast deduplication, then sort the smaller list explicitly.

• Kaushal28: can you give an example of HashSet?
• maaartinus: I wouldn't call it unlikely. There are currently at least two accepted answers of mine recommending against simple println in a loop.
• rdllopes: In terms of complexity, removing duplicates and sorting is the same order as filling up a TreeSet: O(n log n).
• 200_success: @rdllopes Certain pathological cases are possible. For example, consider 1000 different names followed by the same name 5000 times. In that case, O(1) deduplication would be desirable. Sorting is still O(n log n), but it's a smaller n.