<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> diag_order;
        diag_order.reserve(mat.size() * mat.front().size());

        for (int n = 0; n < mat.size() + mat.front().size() - 1; ++n) {
            if (n % 2 == 0) {
                int r = n, c = 0;
                if (n >= mat.size()) {
                    int diff = n + 1 - mat.size();
                    r -= diff;
                    c += diff;
                }

                // cout << "even n " << n << " (" << r << " " << c << ")" << endl;
                while (r >= 0 && r < mat.size() && c >= 0 && c < mat.front().size()) {
                    diag_order.push_back(mat[r][c]);
                    r -= 1;
                    c += 1;
                }
            } else {
                int r = 0, c = n;
                if (n >= mat.front().size()) {
                    int diff = n + 1 - mat.front().size();
                    r += diff;
                    c -= diff;
                }

                // cout << "odd n " << n << " (" << r << " " << c << ")" << endl;
                while (r >= 0 && r < mat.size() && c >= 0 && c < mat.front().size()) {
                    diag_order.push_back(mat[r][c]);
                    r += 1;
                    c -= 1;
                }
            }
        }

        return diag_order;
    }
};
21271