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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[][] DiagonalSort(int[][] mat) {
6 var diagonals = new Dictionary<int, List<int>>();
7 int m = mat.Length, n = mat[0].Length;
8
9 for (int i = 0; i < m; ++i)
10 for (int j = 0; j < n; ++j) {
11 int d = i - j;
12 if (!diagonals.ContainsKey(d)) {
13 diagonals[d] = new List<int>();
14 }
15 diagonals[d].Add(mat[i][j]);
16 }
17
18 foreach (var key in diagonals.Keys) {
19 diagonals[key].Sort();
20 }
21
22 for (int i = 0; i < m; ++i)
23 for (int j = 0; j < n; ++j) {
24 int d = i - j;
25 mat[i][j] = diagonals[d][^1];
26 diagonals[d].RemoveAt(diagonals[d].Count - 1);
27 }
28
29 return mat;
30 }
31}This C# implementation uses a Dictionary and a List to store diagonal elements. After sorting diagonal lists, we refill 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
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.