Radix sort is a sorting algorithm based on counting sort. If you are not familiar with counting sort, please check my previous article first.

If we want to use counting sort, we need to know the bound of numbers. Radix sort use 10 as the bound, and sort numbers in each digits by counting sort.

For example, Say we have an array [75, 45, 9, 123]. We first use counting sort on least digit, which is [5,5,9,3], then we get array [123, 75, 45, 9]. Then use counting sort again on second digit, which is [2,7,4,0], then we get [9, 123, 45, 75]. Note that if that digit is empty, then use 0. Then again, until to the last digit.

[75, 45, 9, 123]
[123, 75, 45, 9]
[9, 123, 45, 75]
[9, 45, 75, 123]

So basically, radix sort is just a for loop with a counting sort inside. If you already know how the counting sort works, then it is easy. Let's see the code.

function radixSort(nums: number[]) {

    let exp = 1;

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

    const getIdx = (i: number) => Math.trunc(nums[i] / exp) % 10;

    let maxVal = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }

    let times = Math.floor(Math.log10(maxVal)) + 1;

    while (times-- > 0) {
        // basic counting sort process

        const count: number[] = Array.from({ length: 10 }, _ => 0);

        // count table
        for (let i = 0; i < nums.length; i++) {
            count[getIdx(i)] += 1;
        }

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

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

        for (let i = 0; i < nums.length; i++) {
            nums[i] = aux[i];
        }

        // next radix
        exp *= 10;
    }
}

Now we know the algorithm, let's solve the leetcode Maximum Gap problem with it.

function maximumGap(nums: number[]): number {
    if (nums.length < 2) return 0;
    if (nums.length === 2) return Math.abs(nums[1] - nums[0]);

    radixSort(nums);

    let maxGap = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        const currentGap = nums[i + 1] - nums[i];
        if (currentGap > maxGap) {
            maxGap = currentGap;
        }
    }
    return maxGap;
};