LeetCode 1329 - Sort the Matrix Diagonally
The problem asks us to sort every diagonal of a matrix independently in ascending order. A diagonal is defined as a sequence of cells that begins either from the first row or the first column, then continues by repeatedly moving one row down and one column to the right.
Difficulty: 🟡 Medium
Topics: Array, Sorting, Matrix
Solution
Problem Understanding
The problem asks us to sort every diagonal of a matrix independently in ascending order. A diagonal is defined as a sequence of cells that begins either from the first row or the first column, then continues by repeatedly moving one row down and one column to the right.
For example, in a matrix:
1 2 34 5 67 8 9
The diagonal starting at position (0, 0) contains the values [1, 5, 9], while the diagonal starting at (0, 1) contains [2, 6].
The input is a two-dimensional integer matrix mat with m rows and n columns. The task is to sort each diagonal independently while preserving the overall matrix shape. After sorting a diagonal, the values must be written back into their original diagonal positions.
The constraints tell us that both dimensions are at most 100, which means the matrix contains at most 10,000 cells. This is small enough that sorting each diagonal independently is completely feasible. Since each matrix element belongs to exactly one diagonal, an O(m * n log(min(m, n))) style solution is efficient enough.
Several edge cases are important to recognize upfront. A matrix with only one row or one column already has diagonals of length 1, so no sorting changes anything. Another edge case is when multiple diagonals have repeated values, because the implementation must still correctly preserve sorted ordering. Rectangular matrices also require careful handling because diagonals can have different lengths.
Approaches
Brute Force Approach
A brute-force solution would repeatedly scan the matrix and attempt to reorder diagonals through swapping operations, similar to repeatedly applying a bubble sort along each diagonal.
For every diagonal, we could repeatedly compare adjacent diagonal elements and swap them if they are out of order. This approach is correct because repeated adjacent swaps eventually sort the diagonal.
However, this method is inefficient because each diagonal may require many passes before becoming sorted. If a diagonal has length k, bubble sorting it costs O(k^2). Since the matrix may contain many diagonals, the total runtime becomes unnecessarily large.
Optimal Approach
The key observation is that every matrix cell belongs to exactly one diagonal, and diagonals are completely independent from one another. This means we can process each diagonal separately.
Instead of repeatedly swapping elements, we can:
- Extract all values from a diagonal.
- Sort the extracted values.
- Write the sorted values back into the same diagonal positions.
This approach is efficient because modern sorting algorithms are highly optimized. Each matrix element is visited only a small number of times.
An important property helps identify diagonals cleanly. Any cells belonging to the same top-left to bottom-right diagonal share the same value of:
row - column
For example:
(0,0) -> 0(1,1) -> 0(2,2) -> 0
All belong to the same diagonal.
We can therefore group elements using a hash map where the key is row - column.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(m * n * min(m, n)^2) | O(1) | Repeated swapping along diagonals |
| Optimal | O(m * n log(min(m, n))) | O(m * n) | Group diagonals, sort once, rewrite values |
Algorithm Walkthrough
- Create a hash map where the key is
row - columnand the value is a list containing all numbers from that diagonal.
This works because every element on the same diagonal has the same difference between row and column indices. 2. Traverse the matrix once.
For every cell (row, column), compute row - column and append the matrix value into the corresponding diagonal list.
3. Sort every diagonal list.
Each list now contains all values from one diagonal. Sorting the list independently guarantees that the diagonal values will later appear in ascending order. 4. Reverse each sorted list.
Reversing allows efficient removal using pop() from the end in Python. Since pop() from the end is O(1), this avoids expensive front removals.
5. Traverse the matrix again.
For each cell (row, column), compute the same diagonal key row - column. Remove the next smallest value from that diagonal list and place it back into the matrix.
6. Return the modified matrix.
At this point, every diagonal has been independently sorted.
Why it works
The algorithm works because all elements sharing the same row - column value belong to the same diagonal and no other diagonal. By collecting all values for each diagonal, sorting them, and then writing them back in traversal order, every diagonal becomes sorted independently while preserving the matrix structure.
Python Solution
from collections import defaultdictfrom typing import List
class Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: rows = len(mat) cols = len(mat[0]) diagonals = defaultdict(list) # Collect values for each diagonal for row in range(rows): for col in range(cols): diagonals[row - col].append(mat[row][col]) # Sort each diagonal in descending order # so we can efficiently pop from the end for key in diagonals: diagonals[key].sort(reverse=True) # Rebuild matrix with sorted diagonal values for row in range(rows): for col in range(cols): mat[row][col] = diagonals[row - col].pop() return mat
The implementation begins by creating a defaultdict(list) to group values belonging to the same diagonal. Using row - col as the key guarantees that all cells from one diagonal end up in the same list.
The first nested loop traverses the matrix and collects values into the appropriate diagonal groups.
After grouping, every diagonal list is sorted in descending order. This detail is important because Python lists support efficient pop() operations only from the end. By reversing the sorted order, the smallest remaining value is always available at the end of the list.
The second matrix traversal reconstructs the matrix. Each cell retrieves the next smallest value from its corresponding diagonal and writes it back into the matrix.
Finally, the modified matrix is returned.
Go Solution
import "sort" func diagonalSort(mat [][]int) [][]int { rows := len(mat) cols := len(mat[0]) diagonals := make(map[int][]int) // Collect values for each diagonal for row := 0; row < rows; row++ { for col := 0; col < cols; col++ { key := row - col diagonals[key] = append(diagonals[key], mat[row][col]) } } // Sort each diagonal in descending order for key := range diagonals { sort.Sort(sort.Reverse(sort.IntSlice(diagonals[key]))) } // Rebuild matrix with sorted values for row := 0; row < rows; row++ { for col := 0; col < cols; col++ { key := row - col diagonal := diagonals[key] lastIndex := len(diagonal) - 1 mat[row][col] = diagonal[lastIndex] diagonals[key] = diagonal[:lastIndex] } } return mat}
The Go implementation follows the same logic as the Python solution. A map[int][]int groups values by diagonal key.
One Go-specific detail is that slices do not provide a direct pop() method. Instead, the implementation manually retrieves the last element and shrinks the slice using slicing syntax.
Another important detail is sorting. Go's standard library uses sort.IntSlice combined with sort.Reverse to sort diagonals in descending order.
Since matrix values are small and constraints are limited, integer overflow is not a concern in Go.
Worked Examples
Example 1
Input:mat = [ [3,3,1,1], [2,2,1,2], [1,1,1,2]]
Step 1: Group values by diagonal
| Cell | Key (row - col) | Value |
|---|---|---|
| (0,0) | 0 | 3 |
| (0,1) | -1 | 3 |
| (0,2) | -2 | 1 |
| (0,3) | -3 | 1 |
| (1,0) | 1 | 2 |
| (1,1) | 0 | 2 |
| (1,2) | -1 | 1 |
| (1,3) | -2 | 2 |
| (2,0) | 2 | 1 |
| (2,1) | 1 | 1 |
| (2,2) | 0 | 1 |
| (2,3) | -1 | 2 |
Diagonal groups become:
0 -> [3,2,1]-1 -> [3,1,2]-2 -> [1,2]-3 -> [1]1 -> [2,1]2 -> [1]
Step 2: Sort each diagonal
0 -> [3,2,1]-1 -> [3,2,1]-2 -> [2,1]-3 -> [1]1 -> [2,1]2 -> [1]
These are stored in reverse order internally for efficient popping.
Step 3: Rebuild matrix
The algorithm fills values back diagonally:
Result:[ [1,1,1,1], [1,2,2,2], [1,2,3,3]]
Example 2
Input:[ [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]]
The algorithm extracts every diagonal independently, sorts them, and writes values back.
One example diagonal is:
[11, 55, 36, 25, 5]
After sorting:
[5, 11, 25, 36, 55]
After processing every diagonal, the final matrix becomes:
[ [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]]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m * n log(min(m, n))) | Every element is grouped once and each diagonal is sorted |
| Space | O(m * n) | Additional storage for diagonal groups |
The total number of matrix elements is m * n. Every element is inserted into exactly one diagonal list. Sorting dominates the runtime. The longest possible diagonal has length min(m, n), which leads to the logarithmic sorting factor.
The extra space comes from storing all diagonal values inside the hash map before reconstructing the matrix.
Test Cases
from typing import List
class Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: from collections import defaultdict rows = len(mat) cols = len(mat[0]) diagonals = defaultdict(list) for row in range(rows): for col in range(cols): diagonals[row - col].append(mat[row][col]) for key in diagonals: diagonals[key].sort(reverse=True) for row in range(rows): for col in range(cols): mat[row][col] = diagonals[row - col].pop() return mat
solution = Solution() assert solution.diagonalSort([ [3,3,1,1], [2,2,1,2], [1,1,1,2]]) == [ [1,1,1,1], [1,2,2,2], [1,2,3,3]