We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Performance Improvements:
- used BufferedReader instead of Scanner
- used StringBuffer to do 1 output to console instead of multiple outputs
This code takes 1.11s to pass Testcase #5
importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.io.IOException;importjava.util.HashMap;importjava.util.ArrayList;publicclassSolution{publicstaticvoidmain(String[]args)throwsIOException{finalintmaxValue=100;/* Create HashMap with empty "buckets" to put Strings into */HashMap<Integer,ArrayList<String>>map=newHashMap<>(maxValue);for(inti=0;i<maxValue;i++){map.put(i,newArrayList<String>());}/* Save input */BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));intn=Integer.parseInt(br.readLine());for(inti=0;i<n;i++){String[]pair=br.readLine().split(" ");intkey=Integer.parseInt(pair[0]);Stringvalue=(i<n/2)?"-":pair[1];ArrayList<String>list=map.get(key);list.add(value);}br.close();/* Print output */StringBuffersb=newStringBuffer();for(inti=0;i<maxValue;i++){ArrayList<String>values=map.get(i);for(Stringstr:values){sb.append(str+" ");}}System.out.println(sb);}}
Hi. I originally directly followed the counting sort pseudocode on Wikipedia. However, that pseudocode is very general and meant to work with multiple languages. In Java, the code is cleaner if you use HashMaps instead of arrays to code counting sort. The algorithm I coded is the same as counting sort, including the runtime.
From wikipedia (and others): .. computing a histogram. It then performs a prefix sum computation.
I think the histogram and the prefix sum computation is the essence, to call it a counting sort algorithm. But I dont see it in your solution. What do you think?
Good question. Technically you may be right, but I think whether I can call it counting sort is open to debate. Here is my original version of counting sort that more closely follows the pseudocode on wikipedia in case you were wondering how it would be done in Java. However, I like my new version better.
In my new version, I still attempt to create a histogram, but instead of using an array, I use a HashMap. I believe it's easier to picture a histogram using this HashMap. I still like to label my algorithm as counting sort since it uses a histogram.
You are right, my algorithm technically does not do a prefix sum, and maybe should not be called counting sort since I don't calculate a prefix sum. The point of doing a prefix sum is just to figure out where to place the original elements into our final sorted array. When using a HashMap, getting this information is actually a little easier though and can be done while looping through the HashMap as I do in my code when I "print output".
The Full Counting Sort
You are viewing a single comment's thread. Return to all comments →
Java solution - passes 100% of test cases
From my HackerRank solutions.
Performance Improvements:
- used BufferedReader instead of Scanner
- used StringBuffer to do 1 output to console instead of multiple outputs
This code takes 1.11s to pass Testcase #5
Let me know if you have any questions.
You are not using Counting Sort (a requirement), are you? So your solution is wrong IMO. Am I wrong?
Hi. I originally directly followed the counting sort pseudocode on Wikipedia. However, that pseudocode is very general and meant to work with multiple languages. In Java, the code is cleaner if you use HashMaps instead of arrays to code counting sort. The algorithm I coded is the same as counting sort, including the runtime.
HackerRank solutions.
From wikipedia (and others): .. computing a histogram. It then performs a prefix sum computation.
I think the histogram and the prefix sum computation is the essence, to call it a counting sort algorithm. But I dont see it in your solution. What do you think?
Good question. Technically you may be right, but I think whether I can call it counting sort is open to debate. Here is my original version of counting sort that more closely follows the pseudocode on wikipedia in case you were wondering how it would be done in Java. However, I like my new version better.
In my new version, I still attempt to create a histogram, but instead of using an array, I use a HashMap. I believe it's easier to picture a histogram using this HashMap. I still like to label my algorithm as counting sort since it uses a histogram.
You are right, my algorithm technically does not do a prefix sum, and maybe should not be called counting sort since I don't calculate a prefix sum. The point of doing a prefix sum is just to figure out where to place the original elements into our final sorted array. When using a HashMap, getting this information is actually a little easier though and can be done while looping through the HashMap as I do in my code when I "print output".
HackerRank solutions.