The Full Counting Sort

  • + 1 comment

    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

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.IOException;
    import java.util.HashMap;
    import java.util.ArrayList;
    
    public class Solution {
        public static void main(String [] args) throws IOException {
            final int maxValue = 100;
            
            /* Create HashMap with empty "buckets" to put Strings into */
            HashMap<Integer, ArrayList<String>> map = new HashMap<>(maxValue);
            for (int i = 0; i < maxValue; i++) {
                map.put(i, new ArrayList<String>());
            }
            
            /* Save input */
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) {
                String [] pair = br.readLine().split(" ");
                int key        = Integer.parseInt(pair[0]);
                String value   = (i < n/2) ? "-" : pair[1];
                
                ArrayList<String> list = map.get(key);
                list.add(value);
            }
            br.close();
            
            /* Print output */
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < maxValue; i++) {
                ArrayList<String> values = map.get(i);
                for (String str : values) {
                    sb.append(str + " ");
                }
            }
            System.out.println(sb);
        }
    }
    

    Let me know if you have any questions.

    • + 1 comment

      You are not using Counting Sort (a requirement), are you? So your solution is wrong IMO. Am I wrong?

      • + 1 comment

        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.

        • + 1 comment

          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?

          • + 0 comments

            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.