3446: Sort Matrix by Diagonals #144
Description
Problem Number
3446
Problem Title
Sort Matrix by Diagonals
LeetCode Link
https://leetcode.com/problems/sort-matrix-by-diagonals/description/
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
Algorithm Description:
The algorithm sorts all diagonals of a square matrix independently and places them back into their original diagonal positions.
It divides diagonals into two categories — those starting from the leftmost column (bottom to top) and those starting from the top row (left to right) — and sorts them differently.
Step 1: Extract diagonals starting from the leftmost column (bottom to top)
The process begins from the last row and moves upward.
For each starting cell in the first column, all elements along its diagonal (extending toward the top-right direction) are collected into a temporary list.
Each diagonal list is sorted in ascending order and then reversed to make it descending.
These diagonals are stored in a collection that represents all “left-column-start” diagonals.
Step 2: Extract diagonals starting from the top row (left to right)
The algorithm now begins from the top row, moving from the second column to the last.
For each starting cell in the top row, the diagonal elements (moving downward and rightward) are collected.
Each diagonal is sorted in ascending order and stored in a separate collection.
Step 3: Combine both sets of diagonals
The diagonals obtained from both directions (steps 1 and 2) are merged into a single list representing all diagonals of the matrix, each stored in sorted form (some descending, some ascending).
Step 4: Reconstruct the matrix
The algorithm then iterates through the stored diagonals and places the sorted elements back into the matrix along their original diagonal positions.
The first set of diagonals (those starting from the bottom-left) are filled first, followed by the top-row diagonals.
Each element is inserted back into its corresponding position to form the final, diagonally sorted matrix.
Data Structures used : 1D and 2D vectors
Time complexity : O(n^2 logn)
Space complexity : O(n^2)
Intuition
Intution:
Each diagonal in a matrix is independent — sorting one doesn’t affect any other.
The idea is to treat every diagonal as a small 1D list:
Extract all elements on the diagonal,
Sort them,
Then put them back in the same diagonal positions.
This works because all elements with the same (row - column) index belong to one diagonal, and no two diagonals overlap.
Solution in C++
class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
vector<vector<int>> ans;
vector<int> t;
int cnt = 1;
int j=0;
for(int i=grid.size()-1;i>=0;i--){
int p=i;
while(j < grid.size() && p < grid.size()){
t.push_back(grid[p][j]);
p++;
j++;
}
sort(t.begin(), t.end());
reverse(t.begin(), t.end());
ans.push_back(t);
t.clear();
j=0;
}
vector<vector<int>> a1;
int r = 1;
for(int k=1;k<grid.size();k++){
int q = 0;
int d = r;
while(q < grid.size() && d < grid.size()){
t.push_back(grid[q][d]);
q++;
d++;
}
sort(t.begin(), t.end());
a1.push_back(t);
t.clear();
r++;
}
for(int i=0;i<a1.size();i++){
ans.push_back(a1[i]);
}
j = grid.size()-1;
int p = 0,q=0;
for(int i=grid.size()-1;i>=0;i--){
int r = i;
while(q < ans[p].size()){
grid[r][j] = ans[p][q];
q++;
r++;
j++;
}
j=0;
q=0;
p++;
}
q=0;
j=1;
r=0;
for(int i=1;i<grid.size();i++){
while(q < ans[p].size()){
grid[r][j] = ans[p][q];
q++;
r++;
j++;
}
j=i+1;
r=0;
q=0;
p++;
}
return grid;
}
};