Algorithm
Problem Name: 498. Diagonal Traverse
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
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]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104-105 <= mat[i][j] <= 105
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> findDiagonalOrder(vector < vector<int>>& matrix) {
vector<int>res;
if(matrix.empty()) return res;
int m = matrix.size(), n = matrix[0].size();
vector<pair < int, int>>dir({{-1, 1}, {1, -1}});
DFS(matrix, res, 0, 0, m, n, dir, 0);
return res;
}
void DFS(vector < vector<int>>& matrix, vector<int>& res, int r, int c, int m, int n, vector < pair<int, int>>& dir, int d){
if(res.size() == m * n) return;
res.push_back(matrix[r][c]>;
int R = r + dir[d].first;
int C = c + dir[d].second;
if(R < 0 || C < 0 || R >= m || C >= n){
d = (d + 1) % 2;
if(R < 0 || R >= m) R = r, C = c + 1;
if(C < 0 || C >= n) R = r + 1, C = c;
}
DFS(matrix, res, R, C, m, n, dir, d);
}
};
Input
mat = [[1,2,3],[4,5,6],[7,8,9]]
Output
[1,2,4,7,5,3,6,8,9]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
int dir = 0;
int x = 0;
int y = 0;
int numOfRows = matrix.length;
int numOfCols = matrix[0].length;
int[] ans = new int[numOfRows * numOfCols];
for (int i = 0; i < numOfRows * numOfCols; i++) {
ans[i] = matrix[x][y];
if ((x + y) % 2 == 0) {
if (y == numOfCols - 1) {
x++;
} else if (x == 0) {
y++;
} else {
x--;
y++;
}
} else {
if (x == numOfRows - 1) {
y++;
} else if (y == 0) {
x++;
} else {
x++;
y--;
}
}
}
return ans;
}
}
Input
mat = [[1,2,3],[4,5,6],[7,8,9]]
Output
[1,2,4,7,5,3,6,8,9]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findDiagonalOrder = function(matrix) {
if (!matrix.length || !matrix[0].length) {
return []
}
const m = matrix.length
const n = matrix[0].length
const output = []
for (let sum = 0; sum < = m + n - 2; sum++) {
for (
let i = Math.min(m - 1, sum);
sum % 2 === 0 && isValid(i, sum - i, m, n);
i--
) {
const j = sum - i
output.push(matrix[i][j])
}
for (
let j = Math.min(n - 1, sum);
sum % 2 === 1 && isValid(sum - j, j, m, n);
j--
) {
const i = sum - j
output.push(matrix[i][j])
}
}
return output
}
function isValid(i, j, m, n) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return false
}
return true
}
Input
mat = [[1,2],[3,4]]
Output
[1,2,3,4]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findDiagonalOrder(self, matrix):
i, j, d, res, n, m = 0, 0, 1, [], len(matrix), len(matrix and matrix[0])
while i < n and j < m:
res.append(matrix[i][j])
if j + 1 < m and (i == 0 and d == 1) or (i == n - 1 and d == -1): j, d = j + 1, -d
elif i + 1 < n and (j == 0 and d == -1) or (j == m - 1 and d == 1): i, d = i + 1, -d
elif d == 1: i, j = i - 1, j + 1
else: i, j = i + 1, j - 1
return res
Input
mat = [[1,2],[3,4]]
Output
[1,2,3,4]
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0498_DiagonalTraverse
{
public int[] FindDiagonalOrder(int[][] matrix)
{
if (matrix == null || matrix.Length == 0) return new int[0];
int N = matrix.Length;
int M = matrix[0].Length;
int[] result = new int[N * M];
int row = 0, col = 0;
for (int i = 0; i < result.Length; i++)
{
result[i] = matrix[row][col];
if ((row + col) % 2 == 0)
{
if (col == M - 1) { row++; }
else if (row == 0) { col++; }
else { row--; col++; }
}
else
{
if (row == N - 1) { col++; }
else if (col == 0) { row++; }
else { row++; col--; }
}
}
return result;
}
}
}
Input
mat = [[1,2,3],[4,5,6],[7,8,9]]
Output
[1,2,4,7,5,3,6,8,9]