# 1424. Diagonal Traverse II

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: vector findDiagonalOrder(vector>& nums) { vector ans; unordered_map> keyToNums; // Key = row + col int maxKey = 0; for (int i = 0; i < nums.size(); ++i) for (int j = 0; j < nums[i].size(); ++j) { const int key = i + j; keyToNums[key].push_back(nums[i][j]); maxKey = max(maxKey, key); } for (int i = 0; i <= maxKey; ++i) for (auto it = rbegin(keyToNums[i]); it != rend(keyToNums[i]); ++it) ans.push_back(*it); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int[] findDiagonalOrder(List> nums) { List ans = new ArrayList<>(); Map> keyToNums = new HashMap<>(); // Key = row + col int maxKey = 0; for (int i = 0; i < nums.size(); ++i) for (int j = 0; j < nums.get(i).size(); ++j) { final int key = i + j; keyToNums.putIfAbsent(key, new ArrayList<>()); keyToNums.get(key).add(nums.get(i).get(j)); maxKey = Math.max(key, maxKey); } for (int i = 0; i <= maxKey; ++i) for (int j = keyToNums.get(i).size() - 1; j >= 0; --j) ans.add(keyToNums.get(i).get(j)); return ans.stream().mapToInt(Integer::intValue).toArray(); } }