Sponsored
Sponsored
This approach involves a direct simulation of the diagonal traversal. We use two variables, i and j, to represent the current position in the matrix, and a boolean direction to indicate whether we are moving upwards or downwards diagonally. The process toggles the direction once the boundaries of the matrix are reached, ensuring that the entire matrix is traversed correctly in a zig-zag order.
Time Complexity: O(m * n) as each element is processed once.
Space Complexity: O(m * n) needed for the output array.
1public class Solution {
2 public int[] FindDiagonalOrder(int[][] mat) {
3 if (mat.Length == 0) return new int[0];
4 int m = mat.Length, n = mat[0].Length;
5 int[] result = new int[m * n];
6 int idx = 0, i = 0, j = 0, direction = 1;
7 while (idx < m * n) {
8 result[idx++] = mat[i][j];
9 if (direction == 1) { // Moving up
10 if (j == n - 1) { i++; direction = -1; }
11 else if (i == 0) { j++; direction = -1; }
12 else { i--; j++; }
13 } else { // Moving down
14 if (i == m - 1) { j++; direction = 1; }
15 else if (j == 0) { i++; direction = 1; }
16 else { i++; j--; }
17 }
18 }
19 return result;
20 }
21}C# version navigates the matrix mat similarly to other high-level languages. The indices are updated with the direction variable determining the current traversal path. Array result stores the ordered elements.
This approach leverages a hash map (or dictionary) to collect elements that belong to the same diagonal. The sum of the row and column indices i + j serves as the key, grouping all elements located on the same diagonal. After populating the hash map, we extract and append these elements to the result array, reversing them as needed to maintain the diagonal order.
Time Complexity: O(m * n), visits each element once.
Space Complexity: O(m * n), required for temporary storage for diagonals.
1#include <unordered_map>
using namespace std;
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
unordered_map<int, vector<int>> diagonals;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
diagonals[i + j].push_back(mat[i][j]);
}
}
vector<int> result;
for (int k = 0; k < m + n - 1; ++k) {
if (k % 2 == 0) {
reverse(diagonals[k].begin(), diagonals[k].end());
}
result.insert(result.end(), diagonals[k].begin(), diagonals[k].end());
}
return result;
}C++ solution makes use of unordered_map to collect all elements of the same diagonal, identified by i + j. This allows easy management of diagonal elements for reverse ordering and result aggregation.