In this post, we will solve HackerRank The Full Counting Sort Solution.
Use the counting sort to order a list of strings associated with integers. If two strings are associated with the same integer, they must be printed in their original order, i.e. your sorting algorithm should be stable. There is one other twist: strings in the first half of the array are to be replaced with the character - (dash, ascii 45 decimal).
Insertion Sort and the simple version of Quicksort are stable, but the faster in-place version of Quicksort is not since it scrambles around elements while sorting.
Design your counting sort to be stable.
Example
arr = [[0,’a’],[1,’b’], [0,’c’],[1,’d’]]
The first two strings are replaced with ‘-‘. Since the maximum associated integer is 1, set up a helper array with at least two empty arrays as elements. The following shows the insertions into an array of three empty arrays.
The result is then printed: – c – d.
Function Description
Complete the countSort function in the editor below. It should construct and print the sorted strings.
countSort has the following parameter(s):
- string arr[n][2]: each arr[i] is comprised of two strings, x and s
Returns
– Print the finished array with each element separated by a single space.
Note: The first element of each arr[i], æ, must be cast as an integer to perform the sort.
Input Format
The first line contains n, the number of integer/string pairs in the array arr.
Each of the next n contains [i] and s[i], the integers (as strings) with their associated strings.
Output Format
Print the strings in their correct order, space-separated on one line.
Sample Input
20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
Sample Output
- - - - - to be or not to be - that is the question - - - -
Explanation
The correct order is shown below. In the array at the bottom, strings from the first half of the original array were replaced with dashes.
0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh
sorted = [['-', '-', '-', '-', '-', 'to'], ['be', 'or'], ['not', 'to'], ['be'], ['-', 'that', 'is', 'the'], ['question'], ['-', '-', '-', '-'], [], [], [], []]
The Full Counting Sort C Solution
#include <stdio.h>
#include <string.h>
#define N 1000000
#define MAX 100
static int x[MAX], offs[MAX];
char s[N][11], sorted[N][11];
int numbers[N];
int main(void){
int i, n, num;
char ss[11];
scanf("%d", &n);
for(i = 0; i<n; i++){
scanf("%d %s", &num, ss);
strcpy(s[i], ss);
numbers[i] = num;
x[num]++;
}
int sum = x[0];
for(num=1; num<n; num++){
offs[num] = sum;
sum += x[num];
}
offs[0] = 0;
for(i=0; i<n; i++){
if(i<n/2)
strcpy(sorted[offs[numbers[i]]++], "-");
else
strcpy(sorted[offs[numbers[i]]++], s[i]);
}
for(i=0; i<n; i++){
printf("%s ",sorted[i]);
}
return 0;
}The Full Counting Sort C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<vector<int>> indices(100);
int n, i, j, x, f;
cin >> n;
string ar[n];
for (i = 0; i < n; i++) {
cin >> x >> ar[i];
indices[x].push_back(i);
}
j = n / 2;
f = 1;
for (i = 0; i < 100; i++) {
for (vector<int>::iterator it = indices[i].begin(); it != indices[i].end(); it++) {
x = *it;
if (f == 1) {
f = 0;
} else {
cout << ' ';
}
if (x < n / 2) {
cout << '-';
} else {
cout << ar[x];
}
}
}
return 0;
}The Full Counting Sort C Sharp Solution
using System;
using System.Text;
using System.Collections.Generic;
class Solution
{
public static void Main( string [] args )
{
// bins for counting numbers
const int nBins = 100;
var arrBins = new int[ nBins ];
// word list
var vWordList = new List< StringBuilder >();
for ( int i = 0; i < nBins; ++i )
{
vWordList.Add( new StringBuilder() );
}
// input n
int n = Convert.ToInt32( Console.ReadLine() );
int nHalf = n / 2;
// input Xi
for ( int i = 0; i < n; ++i )
{
var strInputs = Console.ReadLine().Split();
var num = Convert.ToInt32( strInputs[ 0 ] );
++arrBins[ num ];
if ( vWordList[ num ].Length > 0 )
{
vWordList[ num ].Append( ' ' );
}
if ( i < nHalf )
{
vWordList[ num ].Append( "-" );
}
else
{
vWordList[ num ].Append( strInputs[ 1 ] );
}
}
// populate numbers
bool bSpace = false;
for ( int i = 0; i < nBins; ++i )
{
// add spaces
if ( bSpace )
{
Console.Write( ' ' );
}
else
{
bSpace = true;
}
// display bar or word
Console.Write( vWordList[ i ].ToString() );
}
Console.WriteLine();
return;
}
}The Full Counting Sort Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'countSort' function below.
*
* The function accepts 2D_STRING_ARRAY arr as parameter.
*/
public static void countSort(List<List<String>> arr) {
int[] count = new int[100];
for(List<String> list : arr) {
count[Integer.parseInt(list.get(0))]++ ;
}
for(int i = 1 ; i < 100; i++) {
count[i] += count[i-1];
}
String[] s = new String[arr.size()];
for(int i = arr.size() -1 ; i >= 0 ; i--) {
int n = Integer.parseInt(arr.get(i).get(0));
s[count[n]-1] = (i < arr.size() /2) ? "-" : arr.get(i).get(1) ;
count[n]-- ;
}
StringBuilder sb = new StringBuilder();
for(String ss : s) {
if (sb.length() != 0) {
sb.append(" ");
}
sb.append(ss);
}
System.out.println(sb.toString());
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<List<String>> arr = new ArrayList<>();
IntStream.range(0, n).forEach(i -> {
try {
arr.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
Result.countSort(arr);
bufferedReader.close();
}
}The Full Counting Sort JavaScript Solution
function processData(input) {
var input_split = input.split('\n');
var highestVal = 0;
var values = [];
var strings = [];
for(var i = 1; i < input_split.length; i++){
var lnValues = input_split[i].split(' ');
var lnInt = parseInt(lnValues[0]);
if(lnInt > highestVal){
highestVal = lnInt;
}
values.push(lnInt);
strings.push(lnValues[1]);
}
for(var i = 0; i <= highestVal; i++){
for(var j = 0; j < values.length; j++){
if(i == values[j]){
if(j >= values.length / 2){
process.stdout.write(strings[j]+" ");
}else{
process.stdout.write("- ");
}
}
}
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});The Full Counting Sort Python Solution
from collections import defaultdict
MAXNUM = 100
def count_numbers(lst):
return [lst.count(n) for n in range(MAXNUM)]
def sort(lst):
sorted_lst = []
for i, c in enumerate(lst):
if c != 0:
sorted_lst.extend(i for _ in range(c))
return sorted_lst
def count_less_or_equal(lst):
return [sum(lst[:i + 1]) for i, _ in enumerate(lst)]
def associate(sorted_list, words, helper_list):
output = []
curr_index, i = 0, 0
while curr_index < len(sorted_list):
output.extend(words[sorted_list[curr_index]])
curr_index = helper_list[i]
i += 1
return output
n = int(input())
numbers, words = [], defaultdict(list)
for i in range(n):
num, word = input().split()
if i < n / 2:
word = '-'
numbers.append(int(num))
words[int(num)].append(word)
count = count_numbers(numbers)
helper_lst = count_less_or_equal(count)
sorted_numbers = sort(count)
print(' '.join(word for word in associate(sorted_numbers, words, helper_lst)))Other Solutions
