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.
1def findDiagonalOrder(nums):
2 diagonals = {}
3 for i in range(len(nums)):
4 for j in range(len(nums[i])):
5 if (i + j) not in diagonals:
6 diagonals[i + j] = []
7 diagonals[i + j].append(nums[i][j])
8 result = []
9 for k in sorted(diagonals.keys()):
10 result.extend(reversed(diagonals[k]))
11 return resultThis solution uses a dictionary to store elements by their diagonal key. We compute the diagonal key as the sum of row and column indices. For each diagonal, we store elements in a list. Finally, we sort the keys and concatenate the reversed lists (since lower diagonals need to come first in the result).
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.
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& nums) {
7 std::vector<std::tuple<int, int, int>> elements;
8 for (int i = 0; i < nums.size(); ++i) {
9 for (int j = 0; j < nums[i].size(); ++j) {
10 elements.push_back(std::make_tuple(i, j, nums[i][j]));
11 }
12 }
13 std::sort(elements.begin(), elements.end(), [](auto a, auto b) {
14 int sum1 = std::get<0>(a) + std::get<1>(a);
15 int sum2 = std::get<0>(b) + std::get<1>(b);
16 return sum1 == sum2 ? std::get<0>(b) < std::get<0>(a) : sum1 < sum2;
17 });
18 std::vector<int> result;
19 for (auto& elem : elements) {
20 result.push_back(std::get<2>(elem));
21 }
22 return result;
23 }
24};This C++ solution encodes elements of the form (row, column, value) into a vector, sorts the vector by primary diagonal criterion and secondary reversed row criterion, to maintain the correct diagonal traversal sequence in outputs.