Watch 10 video solutions for Sort the Matrix Diagonally, a medium level problem involving Array, Sorting, Matrix. This walkthrough by codestorywithMIK has 15,658 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].
Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.
Example 1:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Example 2:
Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]] Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1001 <= mat[i][j] <= 100Problem Overview: You receive an m x n matrix. Every diagonal that runs from top-left to bottom-right must be sorted independently in ascending order. Elements stay within their original diagonal; only their order changes.
Approach 1: Using HashMap for Diagonals (O(mn log k) time, O(mn) space)
The key observation is that all cells on the same diagonal share the same value of row - col. Use this value as a key in a hash map and group elements belonging to the same diagonal. First pass: iterate through the matrix and push each value into map[row - col]. Second pass: sort each list of diagonal values. Third pass: iterate through the matrix again and pop the smallest element from the corresponding diagonal list to rebuild the matrix in sorted order.
This approach is easy to reason about and clean to implement. The sorting cost comes from sorting each diagonal separately. If the longest diagonal length is k = min(m, n), the total cost becomes O(mn log k). The extra memory stores all matrix elements inside the hash map. This solution relies on concepts from array, matrix, and sorting problems.
Approach 2: In-place Diagonal Sorting without Extra Storage (O(mn * min(m,n)) time, O(1) space)
If memory is constrained, process each diagonal directly inside the matrix. Every diagonal starts either from the first row or the first column. For each starting position, walk along the diagonal and perform an insertion-style ordering: compare the current element with previous elements along that diagonal and swap backward until the order is correct.
This behaves like insertion sort applied to each diagonal. Because each insertion may scan backward along the diagonal, the worst-case time for one diagonal is O(k^2) where k is its length. Across all diagonals, the total runtime becomes roughly O(mn * min(m,n)). The benefit is constant extra memory since the matrix itself stores the sorted values.
Recommended for interviews: The hash map diagonal grouping solution is the expected answer. It demonstrates recognition of the row - col diagonal invariant and applies straightforward sorting. Interviewers like this approach because it balances clarity and performance at O(mn log k). Mentioning the in-place alternative shows deeper understanding of memory tradeoffs and matrix traversal patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap grouping by (row - col) | O(mn log k) | O(mn) | General case. Clean and commonly expected interview solution. |
| In-place diagonal insertion sort | O(mn * min(m,n)) | O(1) | When memory usage must stay constant and matrix size is small. |