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.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>>& mat) {
6 std::unordered_map<int, std::vector<int>> diagonals;
7 int m = mat.size(), n = mat[0].size();
8 for (int i = 0; i < m; ++i) {
9 for (int j = 0; j < n; ++j) {
10 diagonals[i - j].push_back(mat[i][j]);
11 }
12 }
13 for (auto& diag : diagonals) {
14 std::sort(diag.second.begin(), diag.second.end());
15 }
16 for (int i = 0; i < m; ++i) {
17 for (int j = 0; j < n; ++j) {
18 mat[i][j] = diagonals[i - j].back();
19 diagonals[i - j].pop_back();
20 }
21 }
22 return mat;
23}In this C++ solution, an unordered_map is used to group matrix elements by their diagonals. We then sort the elements in each diagonal. Finally, we reinsert sorted elements back into their respective positions in the matrix, by popping from the vectors.
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.
1def diagonalSort(mat):
2 m, n = len(mat), len(mat[0])
3
4 def sort_diagonal(x, y):
5 diag = []
6 i, j = x, y
7 while i < m and j < n:
8 diag.append(mat[i][j])
9 i += 1
10 j += 1
11
12 diag.sort()
13
14 i, j = x, y
15 for value in diag:
16 mat[i][j] = value
17 i += 1
18 j += 1
19
20 for i in range(m):
21 sort_diagonal(i, 0)
22 for j in range(1, n):
23 sort_diagonal(0, j)
24
25 return matThe Python solution employs a helper function to manage diagonal sorting, ensuring direct manipulation on the matrix itself with an intermediate list to sort elements.