Diagonal Traverse Problem


Description

LeetCode Problem 498.

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

1
2
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

1
2
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

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


Sample C++ Code

The index sum (say it is i) of each round is from 0 to n+m-1. If the column index is j, then the row index is i-j. We need to ensure that j is in [0, m-1], and i-j is in [0, n-1]. Then j’s value is between min(i, m-1) and max(i-n+1, 0).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty())
            return {};
        vector<int>res;
        int n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n + m - 1; i++) { 
            if (i & 1) {
                for (int j = min(i, m - 1); j >= max(i - n + 1, 0); j--)
                    res.push_back(matrix[i - j][j]);
            } else {
                for (int j = max(i - n + 1, 0); j <= min(i, m - 1); j++)
                    res.push_back(matrix[i - j][j]);
            }
        }
        return res;
    }
};




Related Posts

Reshape The Matrix Problem

LeetCode 566. In MATLAB, there is a handy function called...

Island Perimeter Problem

LeetCode 463. You are given row x col grid representing...

Diagonal Traverse Problem

LeetCode 498. Given an m x n matrix mat, return...