The Full Counting Sort – HackerRank Solution

In this post, we will solve The Full Counting Sort HackerRank Solution. This problem (The Full Counting Sort) is a part of HackerRank Problem Solving series.

Task

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.

i	string	converted	list
0				[[],[],[]]
1 	a 	-		[[-],[],[]]
2	b	-		[[-],[-],[]]
3	c			[[-,c],[-],[]]
4	d			[[-,c],[-,d],[]]

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], x, 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 x[i] and s[i], the integers (as strings) with their associated strings.

Constraints

• 1 <= n <= 1000000
• n is even
• 1 <= |s| <= 10
• 0 <= x < 100, x ∈ ar
• s[i] consists of characters in the range ascii[a – z]

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'], ['-', '-', '-', '-'], [], [], [], []]

Solution – The Full Counting Sort – HackerRank Solution

C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

// Stable counting sort
// Total runtime: O(n + k), where is n is the number of elements to sort and k is the size of the largest key
int main() {
    int count[100], n, tmp;
    cin>>n;
    int *key = new int[n]; // Holds the keys for each string
    memset(count, 0, sizeof(count)); // Count will tell us the starting index for each key
    string s, *input = new string[n], *output = new string[n];
    
    // Read input, while calculating key frequencies
    for(int i = 0; i < n; i++) {
        cin>>tmp;
        count[tmp]++; // Count the number of times each key appears
        cin>>s;
        // Store string in an array, following the rules of the problem (the "twist")
        if(i < n/2) {
            input[i] = '-';
        } else {
            input[i]= s;
        }
        key[i] = tmp; // Store the key in an array
    }

    // Calculate the starting index for each key (we did this in the previous challenge)
    int total = 0;
    for(int i = 0; i < 100; i++) {
        total += count[i];
        count[i] = total;
    }

    // Copy to output array, preserving order of inputs with equal keys
    for(int i = n-1; i >= 0; i--) {
        output[count[key[i]]-1] = input[i];
        count[key[i]]--;
    }

    // Print out final array
    for(int i = 0; i < n; i++) {
        cout<<output[i]<<" ";
    }
    return 0;
}

Python

#!/bin/python3

import sys

if __name__ == "__main__":
    n = int(input().strip())
    array = []
    print_dict = {}
    for a0 in range(n):
        x, s = input().strip().split(' ')
        x, s = [int(x), str(s)]
        
        if a0 < n//2:
            array.append((x, "-"))
        else:
            array.append((x, s))
            
    print(" ".join(map(lambda x: x[1], sorted(array, key = lambda x: x[0]))))

Java

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] numbers = new int[n];
        int[] counter = new int[100];
        String[] s = new String[n];
        String[] orderedS = new String[n];
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
            counter[numbers[i]]++;
            s[i] = sc.next();
        }

        for (int i = 1; i < 100; i++) { counter[i] += counter[i-1]; }

        for (int i = (n-1); i >= 0; i--) {
            if (i < n/2) {
                orderedS[counter[numbers[i]] - 1] = "-";
            } else {
                orderedS[counter[numbers[i]] - 1] = s[i];
            }
            counter[numbers[i]] -= 1;
        }

        for (int i = 0; i < n; i++) {
            out.append(orderedS[i] + " ");
        }

        System.out.print(out);
    }
}

Note: This problem (The Full Counting Sort) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.