Sort Matrix by Diagonals solution and explanation
Google
9 more videos on this problem
Sort Matrix by Diagonals | 2 Approaches | Without Map | Leetcode 3446 | codestorywithMIKcodestorywithMIK · 38:17 · 6K views
3446. Sort Matrix by Diagonals | Weekly Contest 436 | Matrix | LeetcodeRapid Syntax · 12:13 · 766 views
3446. Sort Matrix by Diagonals | Leetcode Daily - PythonLeetcode Daily · 5:25 · 592 views
Leetcode 3446. Sort Matrix by Diagonals | Matrix Traversal + Sorting | Python SolutionStatLearn Tech · 14:08 · 586 views
Daily Leetcode #1976: Aug 28, 2025 - 3446. Sort Matrix by DiagonalsProgramming Live with Larry · 15:54 · 487 views
Sort Matrix by Diagonals | Detailed Thought Process | Leetcode 3446 | Medium MarkedCodeWith_Kedar · 10:38 · 343 views
3446. Sort Matrix by Diagonals (Leetcode Medium)Programming Live with Larry · 10:08 · 277 views
LeetCode 3446 | Sort Matrix by Diagonals | Diagonal Sorting Algo | LeetCode Weekly Contest 436AlgoDaily · 14:38 · 261 views
Leetcode 3446 | Sort Matrix by Diagonals | Weekly Contest 436Road To FAANG · 7:07 · 133 views
3446. Sort Matrix by DiagonalsCoding_Hub · 19:42 · 127 views
The problem
You are given an n x n square matrix of integers grid. Return the matrix such that:
- The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order.
- The diagonals in the top-right triangle are sorted in non-decreasing order.
Example 1:
Input: grid = [[1,7,3],[9,8,2],[4,5,6]]
Output: [[8,2,3],[9,6,7],[4,5,1]]
Explanation:
The diagonals with a black arrow (bottom-left triangle) should be sorted in non-increasing order:
[1, 8, 6]becomes[8, 6, 1].[9, 5]and[4]remain unchanged.
The diagonals with a blue arrow (top-right triangle) should be sorted in non-decreasing order:
[7, 2]becomes[2, 7].[3]remains unchanged.
Example 2:
Input: grid = [[0,1],[1,2]]
Output: [[2,1],[1,0]]
Explanation:
The diagonals with a black arrow must be non-increasing, so [0, 2] is changed to [2, 0]. The other diagonals are already in the correct order.
Example 3:
Input: grid = [[1]]
Output: [[1]]
Explanation:
Diagonals with exactly one element are already in order, so no changes are needed.
Constraints:
grid.length == grid[i].length == n1 <= n <= 10-105 <= grid[i][j] <= 105
Approach overview
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.
Solution
We can simulate the diagonal sorting process as described in the problem.
First, we sort the diagonals of the lower-left triangle, including the main diagonal, in non-increasing order. Then, we sort the diagonals of the upper-right triangle in non-decreasing order. Finally, we return the sorted matrix.
The time complexity is O(n^2 log n), and the space complexity is O(n). Here, n is the size of the matrix.
class Solution:
def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
for k in range(n - 2, -1, -1):
i, j = k, 0
t = []
while i < n and j < n:
t.append(grid[i][j])
i += 1
j += 1
t.sort()
i, j = k, 0
while i < n and j < n:
grid[i][j] = t.pop()
i += 1
j += 1
for k in range(n - 2, 0, -1):
i, j = k, n - 1
t = []
while i >= 0 and j >= 0:
t.append(grid[i][j])
i -= 1
j -= 1
t.sort()
i, j = k, n - 1
while i >= 0 and j >= 0:
grid[i][j] = t.pop()
i -= 1
j -= 1
return gridclass Solution {
public int[][] sortMatrix(int[][] grid) {
int n = grid.length;
for (int k = n - 2; k >= 0; --k) {
int i = k, j = 0;
List<Integer> t = new ArrayList<>();
while (i < n && j < n) {
t.add(grid[i++][j++]);
}
Collections.sort(t);
for (int x : t) {
grid[--i][--j] = x;
}
}
for (int k = n - 2; k > 0; --k) {
int i = k, j = n - 1;
List<Integer> t = new ArrayList<>();
while (i >= 0 && j >= 0) {
t.add(grid[i--][j--]);
}
Collections.sort(t);
for (int x : t) {
grid[++i][++j] = x;
}
}
return grid;
}
}class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
int n = grid.size();
for (int k = n - 2; k >= 0; --k) {
int i = k, j = 0;
vector<int> t;
while (i < n && j < n) {
t.push_back(grid[i++][j++]);
}
ranges::sort(t);
for (int x : t) {
grid[--i][--j] = x;
}
}
for (int k = n - 2; k > 0; --k) {
int i = k, j = n - 1;
vector<int> t;
while (i >= 0 && j >= 0) {
t.push_back(grid[i--][j--]);
}
ranges::sort(t);
for (int x : t) {
grid[++i][++j] = x;
}
}
return grid;
}
};/**
* @param {number[][]} grid
* @return {number[][]}
*/
var sortMatrix = function (grid) {
const n = grid.length;
for (let k = n - 2; k >= 0; --k) {
let i = k,
j = 0;
const t = [];
while (i < n && j < n) {
t.push(grid[i++][j++]);
}
t.sort((a, b) => a - b);
for (const x of t) {
grid[--i][--j] = x;
}
}
for (let k = n - 2; k > 0; --k) {
let i = k,
j = n - 1;
const t = [];
while (i >= 0 && j >= 0) {
t.push(grid[i--][j--]);
}
t.sort((a, b) => a - b);
for (const x of t) {
grid[++i][++j] = x;
}
}
return grid;
};function sortMatrix(grid: number[][]): number[][] {
const n = grid.length;
for (let k = n - 2; k >= 0; --k) {
let [i, j] = [k, 0];
const t: number[] = [];
while (i < n && j < n) {
t.push(grid[i++][j++]);
}
t.sort((a, b) => a - b);
for (const x of t) {
grid[--i][--j] = x;
}
}
for (let k = n - 2; k > 0; --k) {
let [i, j] = [k, n - 1];
const t: number[] = [];
while (i >= 0 && j >= 0) {
t.push(grid[i--][j--]);
}
t.sort((a, b) => a - b);
for (const x of t) {
grid[++i][++j] = x;
}
}
return grid;
}public class Solution {
public int[][] SortMatrix(int[][] grid) {
int n = grid.Length;
for (int k = n - 2; k >= 0; --k) {
int i = k, j = 0;
List<int> t = new List<int>();
while (i < n && j < n) {
t.Add(grid[i++][j++]);
}
t.Sort();
foreach (int x in t) {
grid[--i][--j] = x;
}
}
for (int k = n - 2; k > 0; --k) {
int i = k, j = n - 1;
List<int> t = new List<int>();
while (i >= 0 && j >= 0) {
t.Add(grid[i--][j--]);
}
t.Sort();
foreach (int x in t) {
grid[++i][++j] = x;
}
}
return grid;
}
}func sortMatrix(grid [][]int) [][]int {
n := len(grid)
for k := n - 2; k >= 0; k-- {
i, j := k, 0
t := []int{}
for ; i < n && j < n; i, j = i+1, j+1 {
t = append(t, grid[i][j])
}
sort.Ints(t)
for _, x := range t {
i, j = i-1, j-1
grid[i][j] = x
}
}
for k := n - 2; k > 0; k-- {
i, j := k, n-1
t := []int{}
for ; i >= 0 && j >= 0; i, j = i-1, j-1 {
t = append(t, grid[i][j])
}
sort.Ints(t)
for _, x := range t {
i, j = i+1, j+1
grid[i][j] = x
}
}
return grid
}impl Solution {
pub fn sort_matrix(mut grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = grid.len();
if n <= 1 {
return grid;
}
for k in (0..=n - 2).rev() {
let mut i = k;
let mut j = 0;
let mut t = Vec::new();
while i < n && j < n {
t.push(grid[i][j]);
i += 1;
j += 1;
}
t.sort();
let mut i = k;
let mut j = 0;
while i < n && j < n {
grid[i][j] = t.pop().unwrap();
i += 1;
j += 1;
}
}
for k in (1..=n - 2).rev() {
let mut i = k;
let mut j = n - 1;
let mut t = Vec::new();
loop {
t.push(grid[i][j]);
if i == 0 { break; }
i -= 1;
j -= 1;
}
t.sort();
let mut i = k;
let mut j = n - 1;
loop {
grid[i][j] = t.pop().unwrap();
if i == 0 { break; }
i -= 1;
j -= 1;
}
}
grid
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Diagonal Simulation + Sorting | O(m * n log k) | O(k) | Best general approach; simple implementation and minimal extra memory |
| Hash Map Grouping by (row - col) | O(m * n log k) | O(m * n) | Useful when grouping diagonals first simplifies processing logic |
Frequently asked questions
Is Sort Matrix by Diagonals easy or hard?
Sort Matrix by Diagonals is generally considered a medium difficulty problem. The main challenge is identifying how diagonals are traversed and ensuring each diagonal is processed exactly once while keeping the matrix structure intact.
Sort Matrix by Diagonals Python/Java solution
In Python or Java, iterate through diagonal starting points, push elements into a list, sort the list, and rewrite values along the same diagonal. Python typically uses a list with sort(), while Java implementations use ArrayList with Collections.sort().
How to solve Sort Matrix by Diagonals in O(n)?
An exact O(n) solution is not feasible if arbitrary values must be sorted because sorting requires at least O(k log k) comparisons for a diagonal of length k. The practical optimal approach remains O(m * n log k) using simulation and sorting.
What is the best approach for Sort Matrix by Diagonals?
The most practical solution is diagonal simulation with sorting. Start from each diagonal's first cell (first row and first column), collect the values along the diagonal, sort them, and write them back. This runs in O(m * n log k) time where k is the maximum diagonal length and uses O(k) extra space.
Is Sort Matrix by Diagonals asked at Google/Amazon/Meta?
Matrix traversal and diagonal processing problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as diagonal traversal, diagonal sorting, and matrix grouping test indexing logic and array manipulation skills.
What data structure is used in Sort Matrix by Diagonals?
The solution primarily uses arrays or dynamic lists to temporarily store diagonal elements before sorting. Some implementations also use a hash map keyed by row - col to group elements belonging to the same diagonal.
What is the time complexity of Sort Matrix by Diagonals?
The typical solution runs in O(m * n log k) time. Each matrix cell is visited once to gather elements, and each diagonal of length k is sorted using a comparison sort. Since k is at most min(m, n), sorting dominates the runtime.