The Full Counting Sort – Hackerrank Challenge – Java Solution
This is the java solution for the Hackerrank problem – The Full Counting Sort – Hackerrank Challenge – Java Solution.
Source – Ryan Fehr’s repository.
//Problem: https://www.hackerrank.com/challenges/countingsort4 //Java 8 /* Initial Thoughts: We can build a map that has Integer:Queue pairs so that we don' mix up the order of the strings resulting in a stable sort. Then all we need to do is poll from the related queue each time we are printing a number in sorted order Time Complexity: O(n+k) //k is the total numbers and k is total unique numbers Space Complexity: O(k) //we have to intialize an array to the number of unique numbers */ import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); int[] frequencies = new int[100]; StringBuilder STDOUTT = new StringBuilder(""); Map> order = new HashMap<>(); for(int i = 0; i < n; i++) { String[] tmp = in.readLine().split(" "); int num = Integer.parseInt(tmp[0]); StringBuilder s = new StringBuilder(tmp[1]); if(i < n/2) s = new StringBuilder("-");//use - as s for first half //add the string to the queue associated with num if(!order.containsKey(num)) { Queue strs = new LinkedList(); order.put(num, strs); } order.get(num).add(s); frequencies[num] = frequencies[num] + 1; } //For all sorted numbers for(int i = 0; i < frequencies.length; i++) { for(int j = 0; j < frequencies[i]; j++) { STDOUTT.append(order.get(i).poll().toString() + " ");//Print every element from the queue } } System.out.print(STDOUTT); } }