Sponsored
Sponsored
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.
1using System.Collections.Generic;
public class Solution {
public int[][] DiagonalSort(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
for (int i = 0; i < m; ++i) SortAndReplace(mat, i, 0);
for (int j = 1; j < n; ++j) SortAndReplace(mat, 0, j);
return mat;
}
private void SortAndReplace(int[][] mat, int row, int col) {
int m = mat.Length, n = mat[0].Length;
List<int> diag = new List<int>();
int i = row, j = col;
while (i < m && j < n) {
diag.Add(mat[i][j]);
i++; j++;
}
diag.Sort();
i = row; j = col;
foreach (int value in diag) {
mat[i][j] = value;
i++; j++;
}
}
}C# capitalizes on the existing List class and LINQ-based capabilities of sorting for implementing in-place matrix transformation operations, for efficient diagonal rearrangement.