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

&nbsp;
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]


&nbsp;
Constraints:


	m == mat.length
	n == mat[i].length
	1 &lt;= m, n &lt;= 104
	1 &lt;= m * n &lt;= 104
	-105 &lt;= mat[i][j] &lt;= 105


class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        flag, rowNum, colNum = True, len(mat), len(mat[0])

        total, ans = 0, []
        while total <= rowNum + colNum - 2:
            iLimited = rowNum - 1 if flag else colNum - 1 
            jLimited = colNum - 1 if flag else rowNum - 1
            i = total if total < iLimited else iLimited
            j = total - i
            while i >= 0 and j <= jLimited:
                if flag:
                    ans.append(mat[i][j])
                else:
                    ans.append(mat[j][i])
                i -= 1
                j += 1
            total += 1
            flag = not flag
        return ans
/**
 * Simulate Diagonal Order Traversal
 *
 * r+c determines which diagonal you are on. For ex: [2,0],[1,1],[0,2] are all
 * on same diagonal with r+c =2. If you check the directions of diagonals, first
 * diagonal is up, second diagonal is down, third one is up and so on..
 * Therefore (r+c)%2 simply determines direction. Even is UP direction. Odd is
 * DOWN direction.
 *
 * Time Complexity: O(M*N)
 *
 * Space Complexity: O(1) without considering result space.
 *
 * M = Number of rows. N = Number of columns.
 */
class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null) {
            throw new IllegalArgumentException("Input matrix is null");
        }
        if (matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] result = new int[rows * cols];
        int r = 0;
        int c = 0;

        for (int i = 0; i < result.length; i++) {
            result[i] = matrix[r][c];
            if ((r + c) % 2 == 0) { // Move Up
                if (c == cols - 1) {
                    // Reached last column. Now move to below cell in the same column.
                    // This condition needs to be checked first due to top right corner cell.
                    r++;
                } else if (r == 0) {
                    // Reached first row. Now move to next cell in the same row.
                    c++;
                } else {
                    // Somewhere in middle. Keep going up diagonally.
                    r--;
                    c++;
                }
            } else { // Move Down
                if (r == rows - 1) {
                    // Reached last row. Now move to next cell in same row.
                    // This condition needs to be checked first due to bottom left corner cell.
                    c++;
                } else if (c == 0) {
                    // Reached first columns. Now move to below cell in the same column.
                    r++;
                } else {
                    // Somewhere in middle. Keep going down diagonally.
                    r++;
                    c--;
                }
            }
        }

        return result;
    }
}
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int>vec;
        int m=mat.size()-1,n=mat[0].size()-1;
        int i=0,j=0;
        if(m==-1){
            return {};
        }
        if(m==0){
            for(int i{0};i<=n;++i){
                vec.push_back(mat.at(0).at(i));
            }
            return vec;
        }else if(n==0){
            for(int i{0};i<=m;++i){
                vec.push_back(mat.at(i).at(0));
            }
            return vec;
        }
        for(int k{0};k<=m+n;k++){
            if(k==0){
                vec.push_back(mat.at(0).at(0));
                j++;
            }else if(k==m+n){
                vec.push_back(mat.at(m).at(n));
            }else if(k%2!=0){
                while(i<=m && j>=0 && j<=n){
                    vec.push_back(mat.at(i).at(j));
                    i++;
                    j--;
                }
                if(i<=m && j<0){
                    j++;
                }else if(i>m &&j>=0){
                    j+=2;
                    i--;
                }else if(i>m && j<0){
                    i--;
                    j+=2;
                }
                
            }else{
                
                while(i>=0 && j<=n){
                    vec.push_back(mat.at(i).at(j));
                    i--;
                    j++;
                }
                if(i<0 &&j<=n){
                    i++;    
                }else if(i<0 && j>n){
                    i+=2;
                    j--;
                }else if(i>m && j<0){
                    i--;
                    j+=2;
                }else if(i>=0 && j>n){
                    i+=2;
                    j--;
                }
            }
        }
        return vec;
    }
};
var findDiagonalOrder = function(matrix) {
    const res = [];
    for (let r = 0, c = 0, d = 1, i = 0, len = matrix.length * (matrix[0] || []).length; i < len; i++) {
        res.push(matrix[r][c]);
        r -= d;
        c += d;
        if (!matrix[r] || matrix[r][c] === undefined) {                 // We've fallen off the...
            if (d === 1) {
                if (matrix[r + 1] && matrix[r + 1][c] !== undefined) {  // ...top cliff
                    r++;
                } else {                                                // ...right cliff
                    r += 2;
                    c--;
                }
            } else {
                if (matrix[r] && matrix[r][c + 1] !== undefined) {      // ...left cliff
                    c++;
                } else {                                                // ...bottom cliff
                    r--;
                    c += 2;
                }
            }
            d = -d;
        }
    }
    return res;
};
Diagonal Traverse