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.
1import java.util.*;
2
3class Solution {
4 public int[][] diagonalSort(int[][] mat) {
5 Map<Integer, PriorityQueue<Integer>> diagonals = new HashMap<>();
6 int m = mat.length, n = mat[0].length;
7
8 for (int i = 0; i < m; i++) {
9 for (int j = 0; j < n; j++) {
10 diagonals.putIfAbsent(i - j, new PriorityQueue<>());
11 diagonals.get(i - j).add(mat[i][j]);
12 }
13 }
14
15 for (int i = 0; i < m; i++) {
16 for (int j = 0; j < n; j++) {
17 mat[i][j] = diagonals.get(i - j).poll();
18 }
19 }
20
21 return mat;
22 }
23}This Java solution utilizes a HashMap to map diagonals to a min heap (PriorityQueue). Elements are added to respective heaps, and then reinserted into the matrix in sorted order by polling from heaps.
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.