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 rows = mat.size();

        int cols = mat[0].size();

        bool up = true;

        int i = 0, j = 0;

        while (i < rows || j < cols) {

            if (i < 0) {

                up = false;

                i++;

            } else if (j < 0) {

                up = true;

                j++;

            } else {

                if (valid(i, j, mat)) {

                    ans.push_back(mat[i][j]);

                }

                proceed(i, j, up);

            }

        }

        return ans;

    }

    

    bool valid(int i, int j, vector<vector<int>>& mat) {

        if (i < 0 || i >= mat.size() || j < 0 || j >= mat[0].size()) {

            return false;

        }

        return true;

    }

    

    void proceed(int& i, int& j, bool up) {

        if (up) {

            i = i - 1;

            j = j + 1;

        } else {

            i = i + 1;

            j = j - 1;

        }

    }

};