498. Diagonal Traverse
1. Description
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
2. Example
Example 1
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Example 2
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
3. Constraints
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 10$^4$
- 1 <= m * n <= 10$^4$
- -10$^5$ <= mat[i][j] <= 10$^5$
4. Solutions
Simulation
m = matrix.size(), n = matrix.front().size()
Time complexity: O(mn)
Space complexity: O(1)
class Solution {
public:
vector<int> findDiagonalOrder(const vector<vector<int>> &matrix) {
const int m = matrix.size(), n = matrix.front().size();
vector<int> values;
values.reserve(m * n);
int row = 0, column = 0, dir = 0;
array<array<int, 2>, 2> directions{{{-1, 1}, {1, -1}}};
for (int i = 0; i < m * n; ++i) {
values.push_back(matrix[row][column]);
row += directions[dir][0];
column += directions[dir][1];
if (dir == 0 && (row < 0 || column >= n)) {
dir = 1;
if (column >= n) {
row += 2;
column = n - 1;
} else {
row = 0;
}
} else if (dir == 1 && (column < 0 || row >= m)) {
dir = 0;
if (row >= m) {
row = m - 1;
column += 2;
} else {
column = 0;
}
}
}
return values;
}
};