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:

Image text

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()
        }
    }
    
    

All Problems

All Solutions