Leetcode discuss: 1329. Sort the Matrix Diagonally

 Here is the link. 

First practice - C# - Define key as (row - col)

Dec. 21, 2020
Introduction
It is hard to manage my performance on this algorithm. I came out a few ideas to shorten the time in less than 25 minutes to code.

My ideas
I thought about how to define if the position is the first one in diagonal. The naive idea is to check if it is the first one then (row -1, col - 1) should be outside of matrix range. I came cross the idea to define key using row - col, all distinct diagonals can be defined using this value, which is a sequence of rows - 1, rows - 2, ..., - columns + 1 to match from bottom left -> up -> right direction.

Next I thought about using C# List, List.Sort() API to sort the list; To make it easy, I decided to remove the used one from list as well.

Case study
Example:
3, 3, 1, 1,
2, 2, 1, 2,
1, 1, 1, 2

To define diagonal using key value, all positions are marked using key value:
0, -1, -2, -3
1,
2

Use A, B, C, D, E, F, G to mark the order,
0C, -1D, -2E, -3F
1B,
2A
So the key value sequence is [2, 1, 0, -1, -2, -3] to match the order of A, B, C, D, E, F. There are six diagonal lists which start from A or B or C or D or E or F.

Define a hashMap using the above key to identify each distinct diagonal list.

The above positions are head of diagonal list. Next populate the list's key value for each position, position can be determined by it's row - col to match key.
0, -1, -2, -3
1, 0, -1, -2
2, 1, 0, -1

I do think that the above calculation helps me to come out working solution easy and accurate.

My performance
My first practice is to explicitly update hashMap value as a C# List and it takes three statements, which can be simplified by called one statement:

map[key].Sort();

I will figure out how it works and explain to myself.

Production-ready code
I worked on onsite interview feedback, one of feedbacks is to be able to write production-ready code, not just optimized code with a few hints to work with interviewers. It is hard to write production-ready code during onsite interviews.

It is easy to solve another 200 hard level algorithms, I can quickly study top voted discussion post and write C# practice, hopefully I can complete project in less than three months.

Solved algorithms
Right now I only solved 599 algorithms, 238 easy, 289 medium, hard level 72. I like to solve another 200 hard level algorithms.

public class Solution {
    public int[][] DiagonalSort(int[][] mat) {
        if(mat == null || mat.Length == 0 || mat[0].Length == 0)
        {
            return new int[0][];
        }
        
        var rows = mat.Length; 
        var columns = mat[0].Length; 
        
        var sorted = new int[rows][];
        for(int row = 0; row < rows; row++)
        {
            sorted[row] = new int[columns];
        }
        
        var map = new Dictionary<int, List<int>>();        
        
        for(int row = 0; row < rows; row++)
        {
            for(int col = 0; col < columns; col++)
            {
                var key = row - col; 
                if(!map.ContainsKey(key))
                {
                    map.Add(key, new List<int>());
                    
                    int index = 0; 
                    while(row + index < rows && col + index < columns)
                    {
                        map[key].Add(mat[row + index][col + index]);
                        index++;
                    }
                    
					// First writing - explicitly update hashMap value as a C# List<int>
                    // var listTmp = map[key];
                   // listTmp.Sort(); 
                   // map[key]= listTmp; 
				   
				   // After the first submission, the code can be simplified by 
				   // calling Sort(), and it is easy to argue that hashMap will automatically 
				   // keep the sorted list. 
                    map[key].Sort();
                }
                
                var list = map[key];
                sorted[row][col] = list[0];
                list.RemoveAt(0);
                map[key] = list; 
            }            
        }
        
        return sorted; 
    }
}