Sort Matrix by Diagonals

Sort Matrix by Diagonals

What is this problem about?

"Sort Matrix by Diagonals" is a matrix manipulation problem where you are asked to sort the elements within each diagonal of an $N \times N$ matrix. The sorting rules usually differ based on the diagonal's location:

1. Diagonals in the bottom-left triangle (including the main diagonal) should be sorted in non-increasing (descending) order.
2. Diagonals in the top-right triangle should be sorted in non-decreasing (ascending) order.

This problem requires you to correctly identify all diagonals in a 2D grid and apply the correct sorting logic to each group of elements.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask this question to test a candidate's ability to navigate 2D arrays. It evaluates your understanding of grid indices—specifically, how to group elements that belong to the same diagonal (where the difference row - col is constant). It also tests your ability to apply conditional logic and manage multiple sub-tasks (extracting, sorting, and re-inserting) within a single problem.

Algorithmic pattern used

The primary pattern is Diagonal Traversal and Sorting.

1. Identify Diagonals: In any matrix, all elements on the same diagonal have a constant value for row - col.
2. Grouping: Use a Hash Table where the key is the diagonal ID (row - col) and the value is a list of elements on that diagonal.
3. Sorting: Iterate through each list. If the key is $\geq 0$ (bottom-left), sort descending. If the key is $< 0$ (top-right), sort ascending.
4. Re-insertion: Iterate through the matrix again and place the sorted elements back into their respective diagonals.

Example explanation

Input: [[1, 7], [2, 8]]

• Main diagonal (0-0=0): [1, 8]. Sort descending: [8, 1].
• Bottom-left (1-0=1): [2]. Sort descending: [2].
• Top-right (0-1=-1): [7]. Sort ascending: [7]. Result: [[8, 7], [2, 1]]

Common mistakes candidates make

One common mistake is incorrectly identifying the diagonals, especially for non-square matrices (though this problem often uses $N \times N$). Another mistake is applying the wrong sorting order to the wrong triangle. Candidates also sometimes struggle with the "in-place" requirement, accidentally creating many unnecessary copies of the matrix data, which can lead to excessive memory usage.

Interview preparation tip

When you see a matrix diagonal problem, remember the rule: row - col is constant for top-left to bottom-right diagonals, and row + col is constant for top-right to bottom-left diagonals. Mastering this index-based grouping will make any sort matrix by diagonals coding problem much easier to solve. Practice extracting these diagonals into lists and re-filling them to build your confidence with 2D array navigation.