Sort the Matrix Diagonally — Solution in Python, Java & C++
Sort the Matrix Diagonally solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sort the Matrix Diagonally is a medium coding problem on arrays, sorting and matrix, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Matrix
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A matrix diagonal is a run of cells starting on the top row or the leftmost column and going down-right to the edge of the matrix.
Given an m × n matrix mat, sort each diagonal in ascending order and return the result.
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 = [[2,1],[1,2]]
Output: [[2,1],[1,2]]
Explanation: Each diagonal here has at most one out-of-place element.
Example 3
Input: mat = [[9]]
Output: [[9]]
Constraints
1 <= mat.length, mat[i].length <= 81 <= mat[i][j] <= 100
Hints for Sort the Matrix Diagonally
Hint 1
Cells on the same down-right diagonal share the value
r - c. Bucket by it.Hint 2
Sort each bucket, then walk the matrix again writing the sorted values back in order.
Hint 3
Keep a per-diagonal cursor so each bucket is consumed from front to back.
How to solve Sort the Matrix Diagonally
Cells on a down-right diagonal share r - c. Bucket by that key, sort each bucket, and write the sorted values back with a per-diagonal cursor.
Approach
- Group every value by
r - c. - Sort each group.
- Walk the matrix again, emitting the next value from the group for
r - c.
Why it works
The traversal visits each diagonal's cells in top-left to bottom-right order, so consuming each sorted bucket from the front places values in ascending order along the diagonal.
Complexity
- Time —
O(m · n · log(min(m, n))) - Space —
O(m · n)
Pitfalls
- Values are bounded (≤ 100), so a counting sort per bucket removes the log factor.
Reference solution
Python
def diagonalSort(mat):
m, n = len(mat), len(mat[0])
groups = {}
for r in range(m):
for c in range(n):
groups.setdefault(r - c, []).append(mat[r][c])
for key in groups:
groups[key].sort()
cursor = {}
out = []
for r in range(m):
row = []
for c in range(n):
key = r - c
idx = cursor.get(key, 0)
row.append(groups[key][idx])
cursor[key] = idx + 1
out.append(row)
return outJava
public static int[][] diagonalSort(int[][] mat) {
int m = mat.length, n = mat[0].length;
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
groups.computeIfAbsent(r - c, x -> new ArrayList<>()).add(mat[r][c]);
}
}
for (List<Integer> g : groups.values()) Collections.sort(g);
Map<Integer, Integer> cursor = new HashMap<>();
int[][] out = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int key = r - c;
int idx = cursor.getOrDefault(key, 0);
out[r][c] = groups.get(key).get(idx);
cursor.put(key, idx + 1);
}
}
return out;
}C++
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m = (int) mat.size(), n = (int) mat[0].size();
map<int, vector<int>> groups;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) groups[r - c].push_back(mat[r][c]);
}
for (auto& kv : groups) sort(kv.second.begin(), kv.second.end());
map<int, int> cursor;
vector<vector<int>> out(m, vector<int>(n, 0));
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int key = r - c;
out[r][c] = groups[key][cursor[key]];
cursor[key]++;
}
}
return out;
}JavaScript
var diagonalSort = function(mat) {
const m = mat.length, n = mat[0].length;
const groups = new Map();
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
const key = r - c;
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(mat[r][c]);
}
}
groups.forEach(function(arr) { arr.sort(function(a, b) { return a - b; }); });
const cursor = new Map();
const out = [];
for (let r = 0; r < m; r++) {
const row = [];
for (let c = 0; c < n; c++) {
const key = r - c;
const idx = cursor.get(key) || 0;
row.push(groups.get(key)[idx]);
cursor.set(key, idx + 1);
}
out.push(row);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms