The powerful bucket sort

This problem exemplifies one of the best methods to sort out there - bucket sort. Here is the problem: https://leetcode.com/problems/sort-the-matrix-diagonally/

1329. Sort the Matrix Diagonally

Medium

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100

The highlighted line above is the key to solving this problem quickly. The approach first is to create a helper function to sort the contents in the array from (row, col) all the way down to (row+k, col+k) where k increments from one until row+k and col+k are within the limits of the matrix. Since the number allowed in the matrix are in the range 1..100, you can use bucket sort: keep track of the occurrences of each number from 1..100, and then use these counters to sort the values. This is one of the few algorithms for sorting in linear time. Works well. Code is below, cheers, ACC.

public class Solution
{
    public int[][] DiagonalSort(int[][] mat)
    {
        for (int r = mat.Length - 1; r > 0; r--) Sort(mat, r, 0);
        for (int c = 0; c < mat[0].Length; c++) Sort(mat, 0, c);
        return mat;
    }

    private void Sort(int[][] mat,
                        int row,
                        int col)
    {
        int[] bucket = new int[101];

        int tempRow = row;
        int tempCol = col;
        while (row < mat.Length && col < mat[row].Length)
        {
            bucket[mat[row][col]]++;
            row++;
            col++;
        }

        row = tempRow;
        col = tempCol;
        for (int i = 0; i < bucket.Length; i++)
        {
            while (bucket[i] > 0)
            {
                mat[row][col] = i;
                row++;
                col++;
                bucket[i]--;
            }
        }
    }
}