Discussion on Counting Sort 1 Challenge

Sort 414 Discussions, By:

2 weeks ago+ 0 comments

php :

Time Complexity:

The program has two loops. The first loop has a constant number of iterations, i.e., 100 iterations. Therefore, the time complexity of the first loop is O(1).

The second loop has n iterations, where n is the size of the input array. Inside the loop, a constant amount of work is done in each iteration, i.e., incrementing the counter at an index in the frequency array. Therefore, the time complexity of the second loop is O(n).

Thus, the overall time complexity of the program is O(n).

Space Complexity:

The program creates a new array of size 100 to store the frequency counts. Therefore, the space complexity of the program is O(1) for the frequency array.

In addition, the program uses a few constant amount of space to store the input array and some loop variables. Therefore, the space complexity of the program is also O(1) for these variables.

Thus, the overall space complexity of the program is O(1).

function countingSort($arr) {
    // Write your code here
    $res = [];
    for($i=0;$i<100;$i++){
        if(!isset($res[$i])){
            $res[$i] = 0;
        }
    }
    for($i=0;$i<count($arr);$i++){
        $res[$arr[$i]]++;
    }
    return $res;
}

4 weeks ago+ 0 comments

C++ solution

vector<int> countingSort(vector<int> arr) {
vector<int>mp(arr.size());
for(auto it:arr){
    mp[it]++;
}
return mp;
}

2 months ago+ 0 comments

Solution in Python 3

def countingSort(arr):
    arr.sort()
    result = []
    sorted_tuple = tuple(arr)
    for i in range(100):
        value = sorted_tuple.count(i)
        result.append(value)
        
    return result

2 months ago+ 0 comments

def countingSort(a):
    r=[0 for i in range(100)]
    for i in a:
        r[i]+=1
    
    return r

2 months ago+ 0 comments

public static List<Integer> countingSort(List<Integer> arr) {
    
        int[] frequency = new int[100];
        
        for(int i = 0; i < arr.size(); i++) {
            frequency[arr.get(i)] = ++frequency[arr.get(i)];
        }
        
        List<Integer> answer = Arrays.stream(frequency)
                                .boxed()
                                .collect(Collectors.toList());
        
        return answer;
    }

Load more conversations