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 <stdio.h>
2#include <stdlib.h>
3
4#define MAX_DIAGONALS 200000
5
6int* findDiagonalOrder(int** nums, int numsSize, int* numsColSize, int* returnSize) {
7 int** diagonals = malloc(MAX_DIAGONALS * sizeof(int*));
8 int* diagLengths = calloc(MAX_DIAGONALS, sizeof(int));
9 int* result = malloc(100000 * sizeof(int));
10 int count = 0, maxKey = 0;
11 for (int i = 0; i < numsSize; i++) {
12 for (int j = 0; j < numsColSize[i]; j++) {
13 int key = i + j;
14 if (!diagLengths[key]) {
15 diagonals[key] = malloc(5000 * sizeof(int));
16 }
17 diagonals[key][diagLengths[key]++] = nums[i][j];
18 if (key > maxKey) maxKey = key;
19 }
20 }
21 for (int key = 0; key <= maxKey; key++) {
22 for (int i = diagLengths[key] - 1; i >= 0; i--) {
23 result[count++] = diagonals[key][i];
24 }
25 free(diagonals[key]);
26 }
27 free(diagonals);
28 free(diagLengths);
29 *returnSize = count;
30 return result;
31}The C implementation uses dynamic arrays to store elements of diagonals. It assigns elements to diagonals based on the sum of indices (i + j), and afterwards, elements from diagonal structures are reversed into the result array. Proper allocation and deallocation of arrays avoid memory leaks.
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.
1typedef struct {
2 int row, col, value;
3} Element;
4
5int compare(const void *a, const void *b) {
6 Element *ea = (Element *)a;
7 Element *eb = (Element *)b;
8 int sum1 = ea->row + ea->col;
9 int sum2 = eb->row + eb->col;
10 if (sum1 == sum2) {
11 return eb->row - ea->row;
12 }
13 return sum1 - sum2;
14}
15
16int* findDiagonalOrder(int** nums, int numsSize, int* numsColSize, int* returnSize) {
17 Element *elements = malloc(100000 * sizeof(Element));
18 int count = 0;
19 for (int i = 0; i < numsSize; i++) {
20 for (int j = 0; j < numsColSize[i]; j++) {
21 elements[count++] = (Element){i, j, nums[i][j]};
22 }
23 }
24 qsort(elements, count, sizeof(Element), compare);
25 int* result = malloc(count * sizeof(int));
26 for (int i = 0; i < count; i++) {
27 result[i] = elements[i].value;
28 }
29 free(elements);
30 *returnSize = count;
31 return result;
32}The C implementation uses a structure to hold each element with its row, column, and value, sorting them using a custom comparator for diagonal and reverse row criteria, preserving proper sequence for diagonal processing through standard C qsort function.