<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> v;
      if(mat.size() == 1)           // row  = 0      [[1,2,3,4,5]]
    {
        for(int i =0; i<mat[0].size(); i++){
         
        v.push_back(mat[0][i]);
        }

        return v;
    }


if(mat[0].size() == 1)  // col = 0    [[1],[2],[3]]
    {
     for(int i =0; i<mat.size(); i++){
      
          v.push_back(mat[i][0]);
     }

        return v;

    }




      unordered_map<int , vector<int> > mp;
     int max_value_key_store =-1;
      for(int i =0; i<mat.size(); i++)
      {
       
      for(int j =0; j<mat[0].size(); j++)
      {
        mp[i+j].push_back(mat[i][j]);
        max_value_key_store =i+j; // from 0 to max_i+j
      }
      
      }




for(int i=0; i<=max_value_key_store; i++)
{
    vector <int> temp = mp[i];
    
    if(i%2 == 0)
    reverse(temp.begin(), temp.end());
    
    for(int j =0; j<temp.size(); j++){
    v.push_back(temp[j]);
    
    }


}
      return v;
    }
};
23978