Sort the Matrix Diagonally
Medium · Matrix · Array · Matrix · Sorting
Problem
A matrix diagonal starts at a cell in the top row or the left column and runs down and to the right until it leaves the matrix.
Given an m x n integer matrix mat, sort each diagonal in ascending order on its own, so the smallest value ends up at the diagonal's top-left end. Return the resulting matrix.
Examples
Input: mat = [[4,2,9],[1,3,5],[6,7,1]] Output: [[1,2,9],[1,3,5],[6,7,4]]
The main diagonal 4, 3, 1 becomes 1, 3, 4; the diagonals 2, 5 and 1, 7 are already in order.
Input: mat = [[5,1],[3,2],[8,4]] Output: [[2,1],[3,5],[8,4]]
The diagonal (0,0),(1,1) holds 5 and 2 and becomes 2, 5; the diagonal (1,0),(2,1) holds 3 and 4.
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]]
The diagonal from (0,0) holds 3, 2, 1 and becomes 1, 2, 3; the one from (0,1) holds 3, 1, 2 and becomes 1, 2, 3.
Constraints
- m == len(mat), n == len(mat[i])
- 1 <= m, n <= 100
- 1 <= mat[i][j] <= 100
Approaches
- Baseline: bubble along the diagonals — time O(m · n · min(m, n)), space O(1)
Follow-up
The same grouping by i - j answers other diagonal questions: whether every diagonal holds one value (a Toeplitz matrix), or the sum of each diagonal. Grouping by i + j gives the anti-diagonals instead.
Related problems
Start free on Cariara · Coding problems · System design studio
