Sort the Matrix Diagonally

Sort the Matrix Diagonally

What is this problem about?

"Sort the Matrix Diagonally" is a variation of matrix sorting where every diagonal in a 2D matrix (from top-left to bottom-right) must be sorted in ascending order. Unlike some variations, this one typically applies the same sorting rule to every single diagonal in the matrix.

The challenge is to efficiently access all diagonals, sort the elements within them, and then re-populate the matrix. For an $M \times N$ matrix, there are $M + N - 1$ such diagonals.

Why is this asked in interviews?

Companies like Amazon and Walmart Labs ask this to verify that a candidate can work with multidimensional data structures. It tests your ability to identify the relationship between indices in a grid. Specifically, it checks if you know that elements $(r1, c1)$ and $(r2, c2)$ are on the same diagonal if and only if $r1 - c1 = r2 - c2$. It also evaluates your ability to manage collections of data within a matrix.

Algorithmic pattern used

The primary pattern is Hash Map-based Diagonal Sorting.

1. Traversal: Iterate through the entire matrix once.
2. Grouping: Use a Hash Map where the key is row - col. Append each matrix[row][col] to the list corresponding to its key.
3. Sorting: For each list in the map, sort it in ascending order (or use a Min-Heap).
4. Re-filling: Iterate through the matrix again. For each cell, pop the smallest element from the list associated with its row - col and place it in the cell.

Example explanation

Input: [[3, 3, 1, 1], [2, 2, 1, 2], [1, 1, 1, 2]]

• Diagonals:
  • (0,0), (1,1), (2,2): [3, 2, 1] -> Sort: [1, 2, 3]
  • (0,1), (1,2), (2,3): [3, 1, 2] -> Sort: [1, 2, 3] ... Re-filling the matrix with these sorted values gives the result.

Common mistakes candidates make

One common mistake is incorrectly identifying the diagonal keys. Another mistake is not being efficient—some candidates try to find each diagonal one by one starting from the edges, which is much more complex than the simple row - col hash map approach. Finally, forgetting to clear or properly manage the lists of elements as they are popped can lead to reused values or index errors.

Interview preparation tip

Mastering the "Sort the Matrix Diagonally interview question" is all about that one key insight: row - col is the unique ID for a diagonal. Once you have that, the problem becomes a simple application of sorting lists. Practice this grouping technique, as it appears in many other matrix problems like "Toeplitz Matrix" or finding the longest diagonal with a certain property.