• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
vector<int> ans(m * n);
int d = 1;  // left-bottom -> right-top
int row = 0;
int col = 0;

for (int i = 0; i < m * n; ++i) {
ans[i] = matrix[row][col];
row -= d;
col += d;
// out of bound
if (row == m)
row = m - 1, col += 2, d = -d;
if (col == n)
col = n - 1, row += 2, d = -d;
if (row < 0)
row = 0, d = -d;
if (col < 0)
col = 0, d = -d;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
int[] ans = new int[m * n];
int d = 1; // left-bottom -> right-top
int row = 0;
int col = 0;

for (int i = 0; i < m * n; ++i) {
ans[i] = matrix[row][col];
row -= d;
col += d;
// out of bound
if (row == m) {
row = m - 1;
col += 2;
d = -d;
}
if (col == n) {
col = n - 1;
row += 2;
d = -d;
}
if (row < 0) {
row = 0;
d = -d;
}
if (col < 0) {
col = 0;
d = -d;
}
}

return ans;
}
}
``````