<p>Given a 2D integer array <code>nums</code>, return <em>all elements of </em><code>nums</code><em> in diagonal order as shown in the below images</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/08/sample_1_1784.png" style="width: 158px; height: 143px;" />
<pre>
<strong>Input:</strong> nums = [[1,2,3],[4,5,6],[7,8,9]]
<strong>Output:</strong> [1,4,2,7,5,3,8,6,9]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/08/sample_2_1784.png" style="width: 230px; height: 177px;" />
<pre>
<strong>Input:</strong> nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
<strong>Output:</strong> [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i].length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= sum(nums[i].length) &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        ROWS = len(nums)
        COLS = [0] * ROWS
        for r in range(ROWS):
            COLS[r] = len(nums[r])

        q = deque([[0,0]])
        res = []
        visited = set()

        while q:
            lvl_order = []

            for i in range(len(q)):
                r, c = q.popleft()

                if (r is not None and c is not None 
                    and 0 <= r < ROWS and 0 <= c < COLS[r] 
                    and (r, c) not in visited):

                    visited.add((r,c))
                    q.append((r + 1, c))
                    q.append((r, c + 1))

                    lvl_order.append(nums[r][c])

            if lvl_order:
                res.extend(lvl_order)

        return res
        # hashmap = defaultdict(list)
        # res = []

        # for r in range(len(nums)):
        #     for c in range(len(nums[r])):

        #         hash_id = r + c
        #         hashmap[hash_id].append(nums[r][c])

        # # Create an array (ordered by hash_key)
        # diagonals = [d[1] for d in sorted(hashmap.items(), key=lambda x: x[0])] # order by key and return values 
        
        # # reverse and add to res
        # for diagonal in diagonals:
        #     diagonal.reverse()
        #     res.extend(diagonal)
        # return res
43608