<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]:

        # diagonals = defaultdict(list)


        # for i in range(len(nums)):
        #     for j in range(len(nums[i])):
        #         diagonals[i+j].append(nums[i][j])

        # res = []
        # # (m+n) log(m+n)
        # for k in sorted(diagonals.keys()):
        #     res.extend(reversed(diagonals[k]))

        # return res
        
        ROWS, COLS = len(nums), len(nums[0])
        queue = collections.deque([(0,0)])
        visited = set()
        visited.add((0,0))

        res = []
        while queue:
            for _ in range(len(queue)):
                row, col = queue.popleft()
                print ("row: {}, col: {}".format(row, col))
                res.append(nums[row][col])

                if row+1<ROWS and col < len(nums[row+1]) and (row+1, col) not in visited:
                    visited.add((row+1, col))
                    queue.append((row+1, col))

                if row < ROWS and col+1 < len(nums[row]) and (row, col+1) not in visited:
                    visited.add((row, col+1))
                    queue.append((row, col+1))

        return res
        
        
        
43608