Sponsored
Sponsored
The first approach involves using a hashmap or dictionary to store diagonals. For any element at (i, j), the diagonal can be identified by the key (i - j). This key is unique to all elements on the same diagonal. We then collect each diagonal's elements into a list, sort them, and place them back into the matrix.
Time Complexity: O(m * n * log(min(m, n))) due to the sorting of up to min(m, n) elements for each diagonal.
Space Complexity: O(m * n) for storing diagonal elements.
1function diagonalSort(mat) {
2 let map = new Map();
3 let m = mat.length, n = mat[0].length;
4
5 for (let i = 0; i < m; i++) {
6 for (let j = 0; j < n; j++) {
7 let d = i - j;
8 if (!map.has(d)) map.set(d, []);
9 map.get(d).push(mat[i][j]);
10 }
11 }
12
13 for (let key of map.keys()) {
14 map.set(key, map.get(key).sort((a, b) => a - b));
15 }
16
17 for (let i = 0; i < m; i++) {
18 for (let j = 0; j < n; j++) {
19 let d = i - j;
20 mat[i][j] = map.get(d).shift();
21 }
22 }
23
24 return mat;
25}The JavaScript solution involves using a Map to keep diagonals. We sort each diagonal array in-place and update the matrix with sorted values by utilizing shift().
This approach aims to perform cross-diagonal sorting directly within the matrix itself, minimizing additional storage usage. By extracting diagonal elements one at a time, sorting them, and reinserting them, we achieve the diagonal sorting task with constrained space complexity.
Time Complexity: O(m * n * log(min(m, n))) due to sorting operations.
Space Complexity: O(min(m, n)) for temporary diagonal storage.
1
This C code sorts diagonals in place without extra structures. It iterates over each diagonal from top row and left column, extracts, sorts, and reinserts elements back directly.