Counting Sort

Counting sort is an algorithm for sorting an array with positive intergers. The key of counting sort is to use array's index as a kind of tool to help the sort process. Let's take a example to show how the algorithm works.

Say we have an array with values [5, 4, 2, 2, 1, 1, 1, 3]. And we know the elements of array shoud be postive and with a bound of k. Say k is 9.

First we initialize a new array with size as k+1 to store the frequencies of the source array elements.

frequency array
index  0,1,2,3,4,5,6,7,8,9
array [0,0,0,0,0,0,0,0,0,0]

As you can see, I write the frequency array's index explicitly. Because frequency array's index should be the source array's value. Take first element 5 from source array as an example, it should be the the position of index 5 of the frequency array. So we iterate the source array, and fill in the frequency array.

frequency array
index  0,1,2,3,4,5,6,7,8,9
array [0,3,2,1,1,1,0,0,0,0]

As you can see, we got 3 of 2, 2 of 1, 1 of 3, 1 of 4 and 1 of 5. Next, we iterate the whole frequency array. Say in the first iteration, we are at index 0 with value 0, so pass. At next interation, we are at index 1 with value 3, so push 3 elements with value 1 into result array. At next iteration, we are at index 2 with value 2, so push 2 elements with value 2 into result array. Just this kind of oprations, after the iterations end, we should get an result array with ascending sorting order.

Let's see how to implement it in code.

function countingSort(nums: number[], k: number): number[] {
    const frequency = Array.from({length: k+1}, _ => 0);
    for (let i = 0; i < nums.length; i++) {
        frequency[nums[i]] += 1;
    }

    const result: number[] = [];
    for (let i = 0; i < frequency.length; i++) {
        while(frequency[i] > 0) {
            // see here, i is the index of frequency array
            // so i is the value of source array nums
            result.push(i);
            frequency[i] -= 1;
        }
    }

    return result;
}

But in this way, we need to iterate all the number in k range. Actually, a special trick counld be used to only iterate the source nums. First we update the frequency array with prefix sum values. And then this prefix sum values should be the correct index in result array.

frequency array
index        0,1,2,3,4,5,6,7,8,9
array       [0,3,2,1,1,1,0,0,0,0]
prefix sum  [0,3,5,6,7,8,0,0,0,0]

Now take index 5 as an example, its value is 8, then minus 1 to get 7, which is the correct index in result array.

Let's see this trick in code.

function countingSort(nums: number[], k: number): number[] {
    const frequency = Array.from({ length: k + 1 }, _ => 0);
    for (let i = 0; i < nums.length; i++) {
        frequency[nums[i]] += 1;
    }

    const result = Array.from({ length: nums.length }, _ => 0);

    // prefix sum
    for (let i = 1; i < frequency.length; i++) {
        frequency[i] += frequency[i - 1];
    }

    // from back to front
    for (let i = nums.length - 1; i >= 0; i--) {
        result[--frequency[nums[i]]] = nums[i];
    }

    return result;
}

Relative Sort Array

Now we know how counting sort algorithm works, let's use it to solve this leetcode problem.

What is problem demands actually has 2 parts.

The first part, we need to sort arr1 with relative order in line with arr2. This is not hard. We could iterate arr2 and check how many element in arr1 by frequency array. And place all of them in the proper order.

The secord part is actually almost the same with classic counting sort. After first part, we should be left with a frequency array which stores elements' frequency other than elements in arr2. We could iterate this counting array directly and push indexes into result array.

Let's see it in code.

function relativeSortArray(arr1: number[], arr2: number[]): number[] {
    // according to the problem's definition, the max value is 1000
    const frequency = Array.from({ length: 1001 }, (_) => 0);
    for (let i = 0; i < arr1.length; i++) {
        frequency[arr1[i]] += 1;
    }

    const result: number[] = [];
    for (let i = 0; i < arr2.length; i++) {
        const v = arr2[i];
        while (frequency[v] > 0) {
            result.push(v);
            frequency[v] -= 1;
        }
    }

    for (let i = 0; i < frequency.length; i++) {
        while (frequency[i] > 0) {
            result.push(i);
            frequency[i] -= 1;
        }
    }

    return result;
}