In this The Full Counting Sort HackerRank solution, we need to 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
The first two strings are replaced with ‘-‘. Since the maximum associated integer is , 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: .
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 , , must be cast as an integer to perform the sort.
Input Format
The first line contains , the number of integer/string pairs in the array .
Each of the next contains and , the integers (as strings) with their associated strings.
Constraints
is even
consists of characters in the range
Output Format
Print the strings in their correct order, space-separated on one line.
The Full Counting Sort HackerRank Solution
I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.
Problem Solution in JavaScript
function countSort(arr) {
// Replace elements with "-"
for(let i = 0; i < arr.length / 2; i++) arr[i][1] = '-';
// Sorted elemets
const sorted = arr.sort((a, b) => a[0] - b[0]);
// Show elements
console.log(sorted.map(el => el[1]).join(' '));
}Problem Solution in C#
public static void countSort(List<List<string>> arr)
{
SortedList<int, List<string>> resultDict = new SortedList<int, List<string>>();
int half = arr.Count / 2;
for (int i = 0; i < arr.Count; i++)
{
var item = arr[i];
int x = int.Parse(item[0]);
if(i < half)
{
item[1] = "-";
}
if(resultDict.ContainsKey(x))
{
resultDict[x].Add(item[1]);
}
else
{
var entry = new List<string>();
entry.Add(item[1]);
resultDict.Add(x, entry);
}
}
StringBuilder sb = new StringBuilder(arr.Count * 3);
foreach (List<string> strings in resultDict.Values)
{
foreach (string s in strings)
{
sb.Append($"{s} ");
}
}
Console.WriteLine(sb);
}Problem Solution in Python
def countSort(arr):
for i in range(len(arr) // 2):
arr[i][1] = '-'
arr.sort(key=lambda x: int(x[0]))
print(' '.join(x[1] for x in arr))Problem Solution in C++
void countSort(vector<vector<string>> arr) {
map<int, vector<string>> m;
for (int i = 0; i < arr.size(); i++) {
if (i < arr.size() / 2)
m[stoi(arr[i].front())].push_back("-");
else
m[stoi(arr[i].front())].push_back(arr[i].back());
}
for (auto it = m.begin(); it != m.end(); it++) {
for (int i = 0; i < it->second.size(); i++)
cout << it->second[i] << " ";
}
cout.flush();
}