Sort Matrix by Diagonals - Solution & Explanation

Problem Overview: You are given a matrix and need to sort every diagonal independently. Elements that lie on the same top-left to bottom-right diagonal must be reordered while the rest of the matrix structure remains unchanged.

Approach 1: Diagonal Simulation + Sorting (O(m * n log k) time, O(k) space)

Iterate over all diagonals, collect their elements, sort them, and write them back into the matrix. A diagonal is uniquely identified by its starting point on the first row or the first column. From each start cell, walk down-right using (row+1, col+1) until the boundary is reached.

During the traversal, push values into a temporary list. Sort the list using a standard comparison sort, then traverse the same diagonal again and overwrite the matrix cells with the sorted values. The length of each diagonal is at most k = min(m, n), so sorting dominates the cost. This straightforward simulation works well because each cell belongs to exactly one diagonal.

This method relies only on basic iteration and sorting, making it easy to implement in languages like Python, Java, or C++. The matrix itself acts as the final storage while the temporary array holds the elements of a single diagonal at a time.

Approach 2: Hash Map Grouping by Diagonal Index (O(m * n log k) time, O(m * n) space)

Every cell in the matrix belongs to a diagonal identified by the key row - col. Cells with the same difference lie on the same top-left to bottom-right diagonal. Use a hash map where the key is row - col and the value is a list of elements on that diagonal.

First pass: iterate through the matrix and push each value into its diagonal bucket. Second step: sort each bucket individually. Final pass: iterate through the matrix again and place elements back from the corresponding bucket in sorted order. Depending on implementation, you can pop from the front or maintain a pointer.

This approach separates grouping from reconstruction, which can make the logic cleaner when handling many diagonals. The tradeoff is higher memory usage since all diagonal elements are stored simultaneously.

Both approaches rely on fundamentals from array traversal combined with matrix navigation and sorting techniques.

Recommended for interviews: The diagonal simulation approach is usually expected. It demonstrates that you can identify diagonal traversal patterns and apply sorting to substructures of a matrix. Interviewers often appreciate seeing the simple simulation first because it clearly shows the relationship between indices. The hash map grouping version is also acceptable but uses more memory.