<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>>& g) {
        int m = g.size(), n = g[0].size();
        // (i + j) % 2 == 0 -> up, from less j
        // (i + j) % 2 == 1 -> down, from less i
        struct Node{
            int i;
            int j;
            Node(int _i, int _j) : i(_i), j(_j) {}
        };
        vector<Node> v;
        for (int i = 0; i < g.size(); i++) for (int j = 0; j < g[i].size(); j++) v.push_back(Node(i, j));
        auto f = [&g](Node a, Node b) {
            if (a.i+a.j != b.i+b.j) return a.i+a.j < b.i+b.j;
            if ((a.i+a.j) % 2 == 1) {
                return a.i < b.i;
            } else {
                return a.j < b.j;
            }
        };
        sort(v.begin(), v.end(), f);
        vector<int> ans;
        for (auto a : v) ans.push_back(g[a.i][a.j]);
        return ans;
    }
};
23836