The first approach involves using a hashmap or dictionary to store diagonals. For any element at (i, j), the diagonal can be identified by the key (i - j). This key is unique to all elements on the same diagonal. We then collect each diagonal's elements into a list, sort them, and place them back into the matrix.
Time Complexity: O(m * n * log(min(m, n))) due to the sorting of up to min(m, n) elements for each diagonal.
Space Complexity: O(m * n) for storing diagonal elements.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX 101
6
7void sort(int *arr, int size) {
8 for (int i = 0; i < size - 1; i++) {
9 for (int j = 0; j < size - i - 1; j++) {
10 if (arr[j] > arr[j + 1]) {
11 int temp = arr[j];
12 arr[j] = arr[j + 1];
13 arr[j + 1] = temp;
14 }
15 }
16 }
17}
18
19int** diagonalSort(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
20 int diagonals[MAX][MAX];
21 int diagCount[MAX];
22 memset(diagCount, 0, sizeof(diagCount));
23
24 *returnSize = matSize;
25 *returnColumnSizes = matColSize;
26
27 for (int i = 0; i < matSize; i++) {
28 for (int j = 0; j < matColSize[i]; j++) {
29 int d = i - j + 50;
30 diagonals[d][diagCount[d]++] = mat[i][j];
31 }
32 }
33
34 for (int d = 0; d < MAX; d++) {
35 if (diagCount[d] > 0) {
36 sort(diagonals[d], diagCount[d]);
37 }
38 }
39
40 for (int i = 0; i < matSize; i++) {
41 for (int j = 0; j < matColSize[i]; j++) {
42 int d = i - j + 50;
43 mat[i][j] = diagonals[d][matColSize[d]++];
44 }
45 }
46
47 return mat;
48}This C solution uses a hashmap-like approach by leveraging an array diagonals, where the index represents the diagonal identified by (i - j + 50) to ensure positive index values. We first populate this array with elements from each diagonal, sort the array, and write the sorted values back into the matrix.
This approach aims to perform cross-diagonal sorting directly within the matrix itself, minimizing additional storage usage. By extracting diagonal elements one at a time, sorting them, and reinserting them, we achieve the diagonal sorting task with constrained space complexity.
Time Complexity: O(m * n * log(min(m, n))) due to sorting operations.
Space Complexity: O(min(m, n)) for temporary diagonal storage.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5void sort(int *array, int size) {
6 for (int step = 0; step < size - 1; ++step) {
7 for (int i = 0; i < size - step - 1; ++i) {
8 if (array[i] > array[i + 1]) {
9 int temp = array[i];
10 array[i] = array[i + 1];
11 array[i + 1] = temp;
12 }
13 }
14 }
15}
16
17void sortDiagonal(int **mat, int m, int n, int x, int y) {
18 int array[100], idx = 0;
19 int i = x, j = y;
20 while (i < m && j < n) {
21 array[idx++] = mat[i][j];
22 i++; j++;
23 }
24 sort(array, idx);
25 i = x; j = y; idx = 0;
26 while (i < m && j < n) {
27 mat[i][j] = array[idx++];
28 i++; j++;
29 }
30}
31
32int** diagonalSort(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
33 *returnSize = matSize;
34 *returnColumnSizes = matColSize;
35
36 for (int i = 0; i < matSize; i++)
37 sortDiagonal(mat, matSize, *matColSize, i, 0);
38
39 for (int j = 1; j < *matColSize; j++)
40 sortDiagonal(mat, matSize, *matColSize, 0, j);
41
42 return mat;
43}This C code sorts diagonals in place without extra structures. It iterates over each diagonal from top row and left column, extracts, sorts, and reinserts elements back directly.