CODEWITHSUNDEEP
javaoptimizationstring-concatenationcounting-sort
Lei Chen
Lei Chen

Reputation: 719

ways to speed up the Full Counting Sort

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());
    }
}

Upvotes: 6

Views: 1943

Answers (3)

Himanshu singh
Himanshu singh

Reputation: 13

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);
}

Upvotes: 0

user3739478
user3739478

Reputation: 66

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());
 }
}

Upvotes: 4

aioobe
aioobe

Reputation: 420951

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".

Upvotes: 7

Related Questions