This approach uses a hash map (or dictionary) to group elements that belong to the same diagonal. The sum of indices (i + j) of each element forms a unique key for each diagonal. We iterate over the 2D list, store elements based on their diagonal key, and then read each diagonal to form the result in the required traversal order.
Time Complexity: O(N), where N is the total number of elements, as we iterate over each element, and store them in the diagonals dictionary.
Space Complexity: O(N), due to the storage requirement for the diagonals dictionary.
1import java.util.*;
2
3class Solution {
4 public List<Integer> findDiagonalOrder(List<List<Integer>> nums) {
5 Map<Integer, List<Integer>> diagonals = new HashMap<>();
6 int maxKey = 0;
7 for (int i = 0; i < nums.size(); i++) {
8 for (int j = 0; j < nums.get(i).size(); j++) {
9 if (!diagonals.containsKey(i + j)) {
10 diagonals.put(i + j, new ArrayList<>());
11 }
12 diagonals.get(i + j).add(nums.get(i).get(j));
13 maxKey = Math.max(maxKey, i + j);
14 }
15 }
16 List<Integer> result = new ArrayList<>();
17 for (int i = 0; i <= maxKey; i++) {
18 if (diagonals.containsKey(i)) {
19 Collections.reverse(diagonals.get(i));
20 result.addAll(diagonals.get(i));
21 }
22 }
23 return result;
24 }
25}The Java solution uses a HashMap to store lists of elements grouped by their diagonal key (sum of indices). We iterate through the input list to fill the map, keeping track of the maximum diagonal key. We then traverse each key in ascending order, reverse the list stored at that key, and add its contents to the result list.
Another approach is to flatten the 2D matrix into a list of triples containing the row index, column index, and value of each element. We then sort this list, prioritizing the sum of indices (i + j), followed by reversing elements when processed within the same diagonal, ensuring the correct order for traversing.
Time Complexity: O(N log N) due to sorting operation.
Space Complexity: O(N), storing all elements in a list.
1import java.util.*;
2
3class Solution {
4 public int[] findDiagonalOrder(List<List<Integer>> nums) {
5 List<int[]> elements = new ArrayList<>();
6 for (int i = 0; i < nums.size(); i++) {
7 for (int j = 0; j < nums.get(i).size(); j++) {
8 elements.add(new int[]{i, j, nums.get(i).get(j)});
9 }
10 }
11 Collections.sort(elements, (a, b) -> {
12 int cmp = (a[0] + a[1]) - (b[0] + b[1]);
13 return cmp != 0 ? cmp : b[0] - a[0];
14 });
15 int[] result = new int[elements.size()];
16 for (int k = 0; k < elements.size(); k++) {
17 result[k] = elements.get(k)[2];
18 }
19 return result;
20 }
21}The Java solution collects elements with their indices into a list, which it sorts first by diagonal (i.e., the sum of indices), and secondly by row index, reversed. This permits easy creation of the result as values are extracted in final order.