Given a two-dimensional integer matrix, sort each of the diagonals descending from left to right in ascending order.
Constraints
n, m ≤ 25 where n and m are the rows and columns of matrix
Example 1
Input
matrix = [ [9, 8, 7], [6, 5, 4], [3, 2, 1] ]Output
[ [1, 4, 7], [2, 5, 8], [3, 6, 9] ]
Sort and Fill the Diagonals
We can iterate each diagonals (there are R + C – 1 diagonals), store them in a vector, sort the vector, and then re-visit each diagonals to update the value in the diagonal to the sorted version. This will take O((R + C – 1) * D * Log(D)) time where R, C, D are rows, columns, and size of the largest diagonals respectively.
The space complexity is O(D) as we need to copy over the diagonals and sort it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | vector<vector<int>> solve(vector<vector<int>>& matrix) { int rows = matrix.size(); if (0 == rows) return matrix; int cols = matrix[0].size(); for (int r = 0; r < rows; ++ r) { vector<int> d; int y = r, x = 0; while (y < rows && x < cols) { d.push_back(matrix[y][x]); y ++; x ++; } sort(begin(d), end(d)); y = r, x = 0; int i = 0; while (y < rows && x < cols) { matrix[y][x] = d[i ++]; y ++; x ++; } } for (int c = 0; c < cols; ++ c) { vector<int> d; int y = 0, x = c; while (y < rows && x < cols) { d.push_back(matrix[y][x]); y ++; x ++; } sort(begin(d), end(d)); y = 0, x = c; int i = 0; while (y < rows && x < cols) { matrix[y][x] = d[i ++]; y ++; x ++; } } return matrix; } |
vector<vector<int>> solve(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (0 == rows) return matrix;
int cols = matrix[0].size();
for (int r = 0; r < rows; ++ r) {
vector<int> d;
int y = r, x = 0;
while (y < rows && x < cols) {
d.push_back(matrix[y][x]);
y ++;
x ++;
}
sort(begin(d), end(d));
y = r, x = 0;
int i = 0;
while (y < rows && x < cols) {
matrix[y][x] = d[i ++];
y ++;
x ++;
}
}
for (int c = 0; c < cols; ++ c) {
vector<int> d;
int y = 0, x = c;
while (y < rows && x < cols) {
d.push_back(matrix[y][x]);
y ++;
x ++;
}
sort(begin(d), end(d));
y = 0, x = c;
int i = 0;
while (y < rows && x < cols) {
matrix[y][x] = d[i ++];
y ++;
x ++;
}
}
return matrix;
}Using a Priority Queue to do Diagonal Sorting
The elements in the same diagonals have the same value of rowIndex-colIndex. Thus we can use a map to store the key as the diagonals and values would be pushed as we iterate over the matrix:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | vector<vector<int>> solve(vector<vector<int>>& matrix) { map<int, priority_queue<int, vector<int>, greater<int>>> m; int r = matrix.size(); int c = matrix[0].size(); for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { m[i - j].push(matrix[i][j]); } } for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { matrix[i][j] = m[i - j].top(); m[i - j].pop(); } } return matrix; } |
vector<vector<int>> solve(vector<vector<int>>& matrix) {
map<int, priority_queue<int, vector<int>, greater<int>>> m;
int r = matrix.size();
int c = matrix[0].size();
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
m[i - j].push(matrix[i][j]);
}
}
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
matrix[i][j] = m[i - j].top();
m[i - j].pop();
}
}
return matrix;
}The time complexity is O(RCLogD). Space complexity is O(RC).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Introduction to Queue Data Structure and Examples
Next Post: Teaching Kids Programming - Introduction to Venn Graph and Set in Python (Check Unique String)