Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

&nbsp;
Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]


Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i].length &lt;= 105
	1 &lt;= sum(nums[i].length) &lt;= 105
	1 &lt;= nums[i][j] &lt;= 105


class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
		# sort the index of element
        heap = list()
        n = len(nums)
        for i in range(n):
            m = len(nums[i])
            for j in range(m):
                heapq.heappush(heap,[i+j,j,i])
				
		# append the element one by one
        ans = []
        while heap:
            temp = heapq.heappop(heap)
            ans.append(nums[temp[2]][temp[1]])
        return ans
	class Solution {
public int[] findDiagonalOrder(List<List<Integer>> nums) {
    HashMap<Integer , Stack<Integer>> map = new HashMap();
    
    for(int i = 0 ; i < nums.size() ; i++){
        for(int j = 0 ; j < nums.get(i).size() ; j++){
            int z = i + j;
            if(map.containsKey(z)){
                map.get(z).add(nums.get(i).get(j));
            }else{
              Stack<Integer> stk = new Stack<>();
                stk.push(nums.get(i).get(j));
                map.put(z , stk);
            }
        }
    }
    ArrayList<Integer> arr = new ArrayList<>();
    int k = 0;
    while(true){
        if(map.containsKey(k)){
            int size = map.get(k).size();
            while(size-- > 0){
                arr.add(map.get(k).pop());
            }
            k++;
        }else{
            break;
        }
    }
    int[] res = new int[arr.size()];
    for(int i = 0 ; i < res.length ; i++){
        res[i] = arr.get(i);
    }
    
    return res;
}}
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        int n = nums.size();
        int m = 0;
        for(vector<int> &v : nums)
        {
            int y = v.size();
            m = max(m, y);
        }
        vector<int> D2[n+m-1];
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < nums[i].size(); j++)
            {
                D2[i+j].push_back(nums[i][j]);
            }
        }
        vector<int> ans;
        for(int i = 0; i < n+m-1; i++)
        {
            int x = D2[i].size();
            while(x--)
            {
                ans.push_back(D2[i][x]);
                D2[i].pop_back();
            }
        }
        return ans;
    }
};
var findDiagonalOrder = function(nums) {
  let vals = []; // [row, diagonal value, actual value]
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums[i].length; j++) {
      vals.push([i, i + j, nums[i][j]]);
    }
  }
  vals.sort((a, b) => {
    if (a[1] === b[1]) return b[0] - a[0];
    return a[1] - b[1];
  })
  return vals.map(val => val[2]);
};
Diagonal Traverse II