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;
	}
	};

view raw Diagonal Traverse.cpp hosted with ❤ by GitHub