Leetcode discuss: 1329. Sort the Matrix Diagonally

 July 11, 2022

Here is the link. 

C# | Quick learner | Diagonal list - define a key | Using HashMap

Dec. 21, 2020
Introduction
It is challenge to build a sorted matrix based on diagonal list ascending order. How to find all elements in the same diagonal list? Sorting should be straightforward. I like to share my practice starting with definition of a key for each diagonal list.

Example | How to define the key?

I like to explain my design using the above example. Every diagonal list should have a key, and all elements in the same diagonal list should have same value. Since the elements in the same diagonal list increase one in both row and column position. So my definition of list is row - column.

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 there are six keys, {2, 1, 0, -1, -2, -3}, also marked using chars: '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. The order of lists does not matter. If the iteration of matrix is from top to down, left to right, so the iteration will always start from head of list. It is easy to tell that lists are built in the order of C, D, E, F, B, A.

key value matrix for example 1:
0, -1, -2, -3
1, 0, -1, -2
2, 1, 0, -1

Step by step illustration | Example 1
Double for loop, go through row by row, column by column, start from (0,0),

for (int row = 0; row < rows; row++)
{
       for (int col = 0; col < columns; col++)
       {
			// leave blank on purpose
	   }
}

key is 0, and add diagonal list {3, 2, 1} to map[0], and then call map[0].Sort() to sort values in ascending order {1, 2, 3}. Next, put 1 into sorted matrix (0,0) position, and remove first element of map[0] list.

Next is to work on (0, 1) in the mat matrix, and then add {3, 1, 2} to map[-1] as a list. Skip the rest, since it is the same as (0,0) in mat matrix.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1329_sort_matrix
{
    class Program
    {
        static void Main(string[] args)
        {
            var mat = new int[3][];
            mat[0] = new int[] { 3, 3, 1, 1 };
            mat[1] = new int[] { 2, 2, 1, 2 };
            mat[2] = new int[] { 1, 1, 1, 2 };

            var result = DiagonalSort(mat);
            Debug.Assert(string.Join(";", result[0]).CompareTo("1;1;1;1") == 0);
            Debug.Assert(string.Join(";", result[1]).CompareTo("1;2;2;2") == 0);
            Debug.Assert(string.Join(";", result[2]).CompareTo("1;2;3;3") == 0);
        }

        public static 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;

                    // Every list - the start of a new list
                    if (!map.ContainsKey(key))
                    {
                        map.Add(key, new List<int>());

                        // iterate through the list and add all nodes into map[key] list. 
                        int index = 0;
                        while (row + index < rows && col + index < columns)
                        {
                            map[key].Add(mat[row + index][col + index]);
                            index++;
                        }
                       
                        map[key].Sort();
                    }

					// Since all elements in diagonal list with key have been already added to the list, we can add one right away. 
                    // update output matrix - corresponding element's value is updated. 
                    var list = map[key];

                    // always check first one in the list, 
                    // once the node is visited, remove it from the list.
                    sorted[row][col] = list[0];
                    list.RemoveAt(0);
                    map[key] = list;
                }
            }

            return sorted;
        }
    }
}

C# | List.Sort() API | HashMap - Dictionary<int, List>

I also learn to write C# code more efficiently. Originally my code constains the following lines of code:

var listTmp = map[key];
listTmp.Sort();
map[key]= listTmp;

I figured out that the above code can be simplified using one line of statement: 

map[key].Sort();

Please give me upvote. I rewrote the discuss post and make it easy for you to follow.