<p>Given an <code>m x n</code> matrix <code>mat</code>, return <em>an array of all the elements of the array in a diagonal order</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/10/diag1-grid.jpg" style="width: 334px; height: 334px;" />
<pre>
<strong>Input:</strong> mat = [[1,2,3],[4,5,6],[7,8,9]]
<strong>Output:</strong> [1,2,4,7,5,3,6,8,9]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,2],[3,4]]
<strong>Output:</strong> [1,2,3,4]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>4</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= mat[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> ret;
        int row = mat.size();
        if (row == 0) {
            return ret;
        }
        int col = mat[0].size();
        int x = 0;
        int y = 0;
        // upper half
        for (int i = 0; i < col; ++i) {
            vector<int> tmp;
            while (y >= 0 && x < row) {
                tmp.push_back(mat[x][y]);
                x = x + 1;
                y = y - 1;
            }
            
            if (i % 2 == 0) {
                for (int j = tmp.size() - 1; j >= 0; --j )
                    ret.push_back(tmp[j]);
            } else {
                for (int j = 0; j < tmp.size(); ++j)
                    ret.push_back(tmp[j]);
            }
            x = 0;
            y = i + 1;
        }

        x = 1; 
        y = col - 1;
        for (int i = 1; i < row; ++i) {
            vector<int> tmp;
            while (y >= 0 && x < row) {
                cout << "x=" << x << ", y=" << y << endl;
                tmp.push_back(mat[x][y]);
                x = x + 1;
                y = y - 1;
            }
            bool evenReverse = col % 2 == 1 ? true : false;
            cout << "evenReverse=" << evenReverse << endl;
            if (i % 2 == (evenReverse ? 0 : 1)) {
                // reverse tmp and push to ret;
                for (int j = tmp.size() - 1; j >= 0; --j )
                    ret.push_back(tmp[j]);
            } else {
                for (int j = 0; j < tmp.size(); ++j)
                    ret.push_back(tmp[j]);
            }
            x = i + 1;
            y = col - 1;
        }

        return ret;
    }
};
25118