Sort 2D Matrix Diagonally | Coding Interview | Matrix | Sorting

In this article, I have explained the solution for this problem in simple terms.

Sorting the matrix of size m x n diagonally.

The approach is very simple; we have to put elements of each diagonal in a list or some other collection (we will discuss it later), then sort them and put them back in the same diagonal.

Fig 1. put each diagonal into a list and sort them before putting them back in the matrix.

This article is part of the following preparation plan.

30 Days Interview Preparation Plan: 200+ best coding questions and Behavioural interviews

The question is how to access each element of a particular diagonal? And the answer to this problem is that each diagonal in a matrix has a unique I.D. Take any element A[i][j] of a diagonal, then (i-j) is the unique I.D. for that diagonal. In other words, every element A[i][j] of matrix A belongs to the diagonal with the I.D. of i-j.

Then, we can use a hash table and map these I.D.s (i-j) to lists that hold the elements at cell location [i, j] for faster access. From the implementation point of view, we can use HashMap in java, unordered_map in c++, and dict in python.

Fig 2. The diagonal elements are mapped to their I.D.s in the hash table, working as a hash function.

Another thing to note is that instead of using a typical array to store the diagonals, which will take O(DlogD) time to sort where D is the size of the diagonal. We can use min-heaps as the values in our hash table and add an element in O(logD). In this way, we can access the min element of a diagonal while putting back in constant time.

Once all the matrix elements are inserted into the hash table to their corresponding min-heaps, we need to put them back in their original locations in the matrix.