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.
1from collections import defaultdict
2import heapq
3
4def diagonalSort(mat):
5 diagonals = defaultdict(list)
6 m, n = len(mat), len(mat[0])
7
8 for i in range(m):
9 for j in range(n):
10 heapq.heappush(diagonals[i - j], mat[i][j])
11
12 for i in range(m):
13 for j in range(n):
14 mat[i][j] = heapq.heappop(diagonals[i - j])
15
16 return matThe Python solution uses a defaultdict with lists turned into heaps using heapq. After pushing all diagonal elements into respective heaps, they are popped in sorted order 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.