Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/498.html
498. Diagonal Traverse
Level
Medium
Description
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
Explanation:
Note:
The total number of elements of the given matrix will not exceed 10,000.
Solution
The most difficult point is to determine which is the next element. If a border of the matrix is met, then the next element is always to the down or to the right. Consider the cases where each border is met and obtain the next element accordingly.
-
public class Solution { public int[] findDiagonalOrder(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new int[0]; int rows = matrix.length, columns = matrix[0].length; int totalElements = rows * columns; int[] order = new int[totalElements]; int vertical = -1, horizontal = 1; int row = 0, column = 0; for (int i = 0; i < totalElements; i++) { order[i] = matrix[row][column]; row += vertical; column += horizontal; if (row < 0 && column >= columns) { row = 1; column = columns - 1; vertical = 1; horizontal = -1; } else if (row >= rows && column < 0) { row = rows - 1; column = 1; vertical = -1; horizontal = 1; } else if (row < 0) { row = 0; vertical = 1; horizontal = -1; } else if (row >= rows) { row = rows - 1; column += 2; vertical = -1; horizontal = 1; } else if (column < 0) { column = 0; vertical = -1; horizontal = 1; } else if (column >= columns) { column = columns - 1; row += 2; vertical = 1; horizontal = -1; } } return order; } } -
class Solution: def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]: m, n = len(mat), len(mat[0]) ans = [] for k in range(m + n - 1): t = [] i = 0 if k < n else k - n + 1 j = k if k < n else n - 1 while i < m and j >= 0: t.append(mat[i][j]) i += 1 j -= 1 if k % 2 == 0: t = t[::-1] ans.extend(t) return ans ############ class Solution(object): def findDiagonalOrder(self, matrix): """ :type matrix: List[List[int]] :rtype: List[int] """ if not matrix: return [] ans = [] directions = [(-1, 1), (1, -1)] d = 0 i = j = 0 for _ in range(len(matrix) * len(matrix[0])): ans.append(matrix[i][j]) di, dj = directions[d] i, j = i + di, j + dj if i < 0 and 0 <= j < len(matrix[0]): i = 0 elif i >= len(matrix): i = len(matrix) - 1 j -= 2 * dj elif 0 <= i < len(matrix) and j < 0: j = 0 elif 0 <= i < len(matrix) and j >= len(matrix[0]): j = len(matrix[0]) - 1 i -= 2 * di elif i < 0 and j >= len(matrix[0]): i = 1 j -= dj else: continue d = ~d return ans -
class Solution { public: vector<int> findDiagonalOrder(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); vector<int> ans; vector<int> t; for (int k = 0; k < m + n - 1; ++k) { int i = k < n ? 0 : k - n + 1; int j = k < n ? k : n - 1; while (i < m && j >= 0) t.push_back(mat[i++][j--]); if (k % 2 == 0) reverse(t.begin(), t.end()); for (int& v : t) ans.push_back(v); t.clear(); } return ans; } }; -
func findDiagonalOrder(mat [][]int) []int { m, n := len(mat), len(mat[0]) var ans []int for k := 0; k < m+n-1; k++ { var t []int i, j := k-n+1, n-1 if k < n { i, j = 0, k } for i < m && j >= 0 { t = append(t, mat[i][j]) i++ j-- } if k%2 == 0 { p, q := 0, len(t)-1 for p < q { t[p], t[q] = t[q], t[p] p++ q-- } } for _, v := range t { ans = append(ans, v) } } return ans } -
function findDiagonalOrder(mat: number[][]): number[] { const res = []; const m = mat.length; const n = mat[0].length; let i = 0; let j = 0; let mark = true; while (res.length !== n * m) { if (mark) { while (i >= 0 && j < n) { res.push(mat[i][j]); i--; j++; } if (j === n) { j--; i++; } i++; } else { while (i < m && j >= 0) { res.push(mat[i][j]); i++; j--; } if (i === m) { i--; j++; } j++; } mark = !mark; } return res; } -
impl Solution { pub fn find_diagonal_order(mat: Vec<Vec<i32>>) -> Vec<i32> { let (m, n) = (mat.len(), mat[0].len()); let (mut i, mut j) = (0, 0); (0..m * n) .map(|_| { let res = mat[i][j]; if (i + j) % 2 == 0 { if j == n - 1 { i += 1; } else if i == 0 { j += 1; } else { i -= 1; j += 1; } } else { if i == m - 1 { j += 1; } else if j == 0 { i += 1; } else { i += 1; j -= 1; } } res }) .collect() } }