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.
The first approach involves using a hashmap or dictionary to store diagonals. For any element at (i, j), the diagonal can be identified by the key (i - j). This key is unique to all elements on the same diagonal. We then collect each diagonal's elements into a list, sort them, and place them back into the matrix.
This C solution uses a hashmap-like approach by leveraging an array diagonals, where the index represents the diagonal identified by (i - j + 50) to ensure positive index values. We first populate this array with elements from each diagonal, sort the array, and write the sorted values back into the matrix.
Time Complexity: O(m * n * log(min(m, n))) due to the sorting of up to min(m, n) elements for each diagonal.
Space Complexity: O(m * n) for storing diagonal elements.
This approach aims to perform cross-diagonal sorting directly within the matrix itself, minimizing additional storage usage. By extracting diagonal elements one at a time, sorting them, and reinserting them, we achieve the diagonal sorting task with constrained space complexity.
This C code sorts diagonals in place without extra structures. It iterates over each diagonal from top row and left column, extracts, sorts, and reinserts elements back directly.
Time Complexity: O(m * n * log(min(m, n))) due to sorting operations.
Space Complexity: O(min(m, n)) for temporary diagonal storage.
We can treat each diagonal of the matrix as an array, sort these arrays, and then fill the sorted elements back into the original matrix.
Specifically, we denote the number of rows in the matrix as m and the number of columns as n. Since any two elements (i_1, j_1) and (i_2, j_2) on the same diagonal satisfy j_1 - i_1 = j_2 - i_2, we can determine each diagonal based on the value of j - i. To ensure the value is positive, we add an offset m, that is, m - i + j.
Finally, we fill the sorted elements of each diagonal back into the original matrix.
The time complexity is O(m times n times log min(m, n)), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the matrix, respectively.
| Approach | Complexity |
|---|---|
| Using Hashmap for Diagonals | Time Complexity: |
| In-place Sorting without Extra Storage | Time Complexity: |
| Sorting | — |
| 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. |
Sort the Matrix Diagonally | Leetcode 1329 | Similar to Leetcode 498 | codestorywithMIK • codestorywithMIK • 15,658 views views
Watch 9 more video solutions →Practice Sort the Matrix Diagonally with our built-in code editor and test cases.
Practice on FleetCode