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.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7 std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& nums) {
8 std::unordered_map<int, std::vector<int>> diagonals;
9 int maxKey = 0;
10 for (int i = 0; i < nums.size(); ++i) {
11 for (int j = 0; j < nums[i].size(); ++j) {
12 diagonals[i + j].push_back(nums[i][j]);
13 maxKey = std::max(maxKey, i + j);
14 }
15 }
16 std::vector<int> result;
17 for (int i = 0; i <= maxKey; ++i) {
18 if (diagonals.count(i)) {
19 std::reverse(diagonals[i].begin(), diagonals[i].end());
20 result.insert(result.end(), diagonals[i].begin(), diagonals[i].end());
21 }
22 }
23 return result;
24 }
25};The C++ solution employs an unordered_map to collect elements by diagonal key. During insertion, we track the maximum key, which indicates the number of diagonals. After populating diagonals, we reverse each list in preparation for output, adhering to the problem's order requirements.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] FindDiagonalOrder(IList<IList<int>> nums) {
6 var elements = new List<(int, int, int)>();
7 for (int i = 0; i < nums.Count; i++) {
8 for (int j = 0; j < nums[i].Count; j++) {
9 elements.Add((i, j, nums[i][j]));
10 }
11 }
12 elements.Sort((a, b) => {
13 int cmp = (a.Item1 + a.Item2).CompareTo(b.Item1 + b.Item2);
14 if (cmp == 0) {
15 return b.Item1.CompareTo(a.Item1);
16 }
17 return cmp;
18 });
19 var result = new List<int>();
20 foreach (var element in elements) {
21 result.Add(element.Item3);
22 }
23 return result.ToArray();
24 }
25}This C# solution constructs tuples of each element's coordinates and value, sorting these tuples by their diagonal priority and reversed row criteria, in order to properly traverse diagonals in the required system, culminating in extraction and return of the values.