Monday, March 7, 2022

LeetCode 498. Diagonal Traverse

 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.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • -105 <= mat[i][j] <= 105

class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
vector<int> ans;
int n = mat.size();
int m = mat[0].size();
bool left = true;
for(int i = 0; i < m + n - 1; i++){
int x, y, dx, dy;
if(left) {
x = min(i, n - 1);
y = max(0, i - (n - 1));
dx = -1;
dy = 1;
left = false;
}
else {
y = min(i, m - 1);
x = max(0, i - (m - 1));
dx = 1;
dy = -1;
left = true;
}
while(x >= 0 and x < n and y >= 0 and y < m){
ans.push_back(mat[x][y]);
x += dx;
y += dy;
}
}
return ans;
}
};

No comments:

Post a Comment