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

from collections import defaultdict
import heapq 
class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        """
        start at 0,0

        increase up in crease right 
        r c
            row counts down to zero once its zero 
                column counts up 
                    take prev column and add one to it and start there

        0,0 0,1 0,2 0,3
        1,0 1,1 1,2 
        2,0 2,1
        3,0 

        
        """
        result = []
        # if len(nums)==0:
        #     return result

        
        n = 0 
        hm = defaultdict(list)
        max_d = 0 
        for i,row in enumerate(nums):
            for j,v in enumerate(row):
                d = i+j
                heapq.heappush(hm[d],(j,i))

                if d>max_d:
                    max_d = d
        result =[]
        for d in range(max_d+1):
            
            while hm[d]:
                j,i = heapq.heappop(hm[d])
                result.append(nums[i][j])

            
            # print(hm[d])
            # for j,i in hm[d]:
            #     print(j,i,i+j,nums[i][j])
            #     result.append(nums[i][j])
        # print(result)
        return result        

        
                # n+=1
    
        # i = 0 
        # j = 0 
        # d = 0
        # while len(result)<n: #(0,0)

        #     if (i,j) in hm: # (1,0)
        #         result.append(hm[(i,j)])
            
        #     if i==0:
        #         d+=1 #1 
        #         j=0 # 
        #         i=d #(1,0)
        #     else:
        #         i-=1 # 
        #         j+=1 # 
        

        # return result
        


49886