ways to speed up the Full Counting Sort

Question

I encountered a question on hackerrank. https://www.hackerrank.com/challenges/countingsort4

My first attempt passed all the test cases except the last one, due to timeout. After failed to come up with a more efficient algorithm, I improved the code by using StringBuilder instead of concatenating Strings directly. This brought the running time from more than 5 sec to 3.5 sec.

My question is that is there any other way that I can improve the running time? Thanks.

The following is my code.

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        scanner.nextLine();

        int[] oriNum = new int[N];        
        String[] oriStr = new String[N];
        int[] count = new int[100];
        int[] indices = new int[100];
        int[] output = new int[N];

        // save the originals and the count array
        for (int i = 0; i < N; i++) {
            oriNum[i] = scanner.nextInt();
            oriStr[i] = scanner.nextLine().trim();
            count[oriNum[i]]++;
        }

        // accumulate the count array
        indices[0] = 0;
        for (int i = 1; i < 100; i++) {
            indices[i] = indices[i-1] + count[i-1];
        }

        // output order
        for (int i = 0; i < N; i++) {
            int num = oriNum[i];
            output[indices[num]++] = i;
        }

        int bar = N/2;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {            
            int index = output[i];
            if (index < bar) 
                sb.append("- ");
            else 
                sb.append(oriStr[index]+ " ");
        }
        System.out.println(sb.toString());
    }
}

Stratum

Instead of sb.append(oriStr[index]+ " "); use sb.append(oriStr[index]).append(" "); – Jackass

This question appears to be off-topic because it is asking for Code Review and as such belongs on Code Review SE. – Grown

If by any chance you have landed on this thread while searching on how to make counting sort stable as required in the referred HackerRank question then please see this post - How is counting sort a stable sort? – Wreckful

Answer 1

You should try a plain buffered reader instead of Scanner. Scanner is surprisingly slow and I have participated in programming competitions where Scanner was the sole reason for "time limit exceeded".

Director

I tried the BufferedReader, and the running time decreased from 3.5 sec to 1.4 sec. Great suggestion, Thanks! – Stratum

Heh, you're welcome. I've been in the same situation. – Director

Answer 2

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution 
{
    public static void main(String[] args)throws Exception 
{
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(in.readLine());
    int[] c=new int[100];
    String[][] dt=new String[100][10300];
    for(int i=0;i<n;i++)
    {
        String[] str=in.readLine().split(" ");
        int val=Integer.parseInt(str[0]);
        if(i<n/2)
            dt[val][c[val]]="-";
        else
             dt[val][c[val]]=str[1];
        c[val]++;
     }
  StringBuilder sb=new StringBuilder("");
    for(int i=0;i<100;i++)
       if(i<n)
        for(int k=0;k<c[i];k++)
            if(dt[i][k]!=null)
               sb.append(dt[i][k]+" ");
            else break;
    System.out.println(sb.toString());
 }
}

Shevat

Answer 3

This was my approach to problem. (it is in c++).

void counting_sort(vector<int> &arr, int size,  vector<vector<string> > foo, vector<int> first_half)
{
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());

    int range = max - min + 1;

    int count[range] = {0};

    // counting frequency of numbers in array
    for (int i = 0; i < size; i++)
    {
        count[arr[i] - min]++;
    }

    // calculating cumulative sum
    for (int i = 1; i < range; i++)
    {
        count[i] += count[i - 1];
    }

    vector<vector<string> > output(size);

    // making the new sorted array
    for (int i = size - 1; i >= 0; i--) // traversing from backward for stability
    {
        output[count[arr[i]-min] - 1] = foo[i];
        count[arr[i]-min]--;
    }

    // copying the sorted array in original array
    int j=0;
    for (int i = 0; i < size; i++)
    {
        if(stoi(output[i][0]) == first_half[j])
        {
            cout << "- ";
            j++;
        }
        else
        {
            cout << output[i][1] << ' ';
        }
    }
}

// Complete the countSort function below.
void countSort(vector<vector<string>> arr) {

    vector<int> num;
    vector<int> first_half;
    for(int i=0; (unsigned)i<arr.size(); i++)
    {
        num.push_back(stoi(arr[i][0]));
        if(i < ((unsigned)arr.size()/2))
        {
            first_half.push_back(stoi(arr[i][0]));
        }
    }

    sort(first_half.begin(), first_half.end());
    counting_sort(num, num.size(), arr, first_half);
}

Sheol