LeetCode [498] Diagonal Traverse

498. Diagonal Traverse

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: vector<int> findDiagonalOrder(vector<vector<int>>& matrix) { vector<int> ret; int m = matrix.size(); if(m==0) return ret; int n = matrix[0].size(); if(n==0) return ret; for(int s=0; s<=m+n-2; ++s){ vector<int> line; for(int j = max(0, s - (m-1)); j < n; ++j){ int i = s-j; if(i<0) break; line.push_back(matrix[i][j]); } if(s%2==1) reverse(line.begin(), line.end()); ret.insert(ret.end(), line.begin(), line.end()); } return ret; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public int[] findDiagonalOrder(int[][] matrix) { int m = matrix.length; if(m==0) return new int[0]; int n = matrix[0].length; if(n==0) return new int[0]; int[] ret = new int[m*n]; int r = 0, c = 0; for(int i=0; i<m*n; ++i){ ret[i] = matrix[r][c]; if((r+c)%2 == 0){//moving up if(c==n-1) r++; else if(r == 0) c++; else {r--; c++;} }else{//moving down if(r==m-1) c++; else if(c==0) r++; else {r++; c--;} } } return ret; } }