1329. Sort the Matrix Diagonally
Problem Description
The task is to sort the integers in each diagonal of a given m x n
matrix mat
. A matrix diagonal is defined as a line of cells that starts from a cell in either the topmost row or leftmost column and goes diagonally in the bottom-right direction until it reaches the end of the matrix. The sorting of each diagonal should be done in ascending order, and the goal is to return the matrix with all diagonals sorted.
For instance, if a diagonal starts from mat[2][0]
in a 6 x 3
matrix, it would include the cells mat[2][0]
, mat[3][1]
, and mat[4][2]
. This diagonal, like all others in the matrix, needs to be sorted so that the smallest number is at mat[2][0]
and the largest at mat[4][2]
.
Intuition
To solve the problem, we understand that each diagonal can be sorted independently of the others, since the sorting of one diagonal does not affect the elements in another diagonal.
A brute force approach to sort each diagonal is to use a "bubble sort"-like method where for each diagonal, we perform a series of comparisons and swaps until each element on the diagonal is in ascending order. The solution code provided is based on this approach.
Here's how we approach it:
-
Iterate over each possible starting cell of a diagonal. This would usually mean iterating over cells on the top row and the leftmost column, but the code provided is only iterating through
min(m, n)
elements. This part of the approach seems to be limiting the number of iterations and may not cover all diagonals in a non-square matrix (wherem
is not equal ton
). -
Perform a double loop, iterating through cells within the matrix boundaries, excluding the last row and column, to compare the current cell
mat[i][j]
with the next cell in the diagonalmat[i+1][j+1]
. -
If the current cell is larger than the next cell in the diagonal, we swap them. The swap ensures that the smaller value moves towards the start of the diagonal.
-
Repeat the comparison and swapping process until all cells in the matrix are checked. Note that this requires multiple passes through the matrix to get all elements in the correct order, given the nature of the "bubble sort"-like method.
This solution ensures each diagonal is sorted, but it's not the most efficient approach due to its high time complexity, and it's not optimized to handle non-square matrices correctly in all cases.
Learn more about Sorting patterns.
Solution Approach
The code provided uses a simplified in-place sorting algorithm similar to bubble sort to sort each diagonal of the matrix.
Let's walk through the implementation step by step:
-
The first step is to retrieve the dimensions of the matrix using
len(mat)
for the number of rows (m
) andlen(mat[0])
for the number of columns (n
). -
It then uses a nested loop to iterate over the elements of the matrix, excluding the last row and column to prevent out-of-bounds access. The loop variables
i
andj
represent the current cell being considered. -
The code compares each element
mat[i][j]
with the next diagonal elementmat[i + 1][j + 1]
. When it finds thatmat[i][j]
is greater thanmat[i + 1][j + 1]
, it performs a swap. This operation is intended to move the larger numbers down and right along the diagonals and the smaller numbers up and left. -
However, the provided solution approach only iterates through the diagonals that start in the cells
[0, k]
fork < min(m, n)
. This is a simplification and does not sort all diagonals properly in the case of non-square matrices, since it doesn't address all possible starting cells of the diagonals that could be on the leftmost column for a matrix wherem > n
. -
The code will perform the comparison and swapping process repeatedly in a brute force manner, iterating over the matrix cells
m - 1
times to ensure all cells are eventually sorted. Since bubble sort has a time complexity of O(N^2), the time complexity of this code will also reflect the inefficiencies of bubble sort, especially as the size of the matrix grows.
To sum up, the solution attempts to use a bubble sort-like algorithm over the matrix's diagonals to sort each one in ascending order. The problem with this implementation is that it may not sort all diagonals as desired, especially for non-square matrices, and it's not efficient due to the bubble sort approach resulting in a high time complexity.
Note that a more efficient solution would sort each diagonal individually by extracting the diagonal elements, sorting them using a more efficient sorting algorithm (e.g., quicksort or timsort), and then placing them back into the matrix. This approach would significantly reduce the overall time complexity to O(DlogD) for each diagonal of average length D.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a simple example to illustrate the solution approach described. Consider the following 3x3
matrix mat
:
1mat = [ 2 [3, 3, 1], 3 [2, 2, 2], 4 [1, 1, 1] 5]
The goal is to sort the integers in each diagonal. In this matrix, there are five diagonals:
- The first diagonal starting from
mat[0][0]
includes the elements[3]
(already sorted). - The second diagonal starting from
mat[0][1]
includes the elements[3, 2]
. - The third diagonal starting from
mat[0][2]
includes the elements[1, 2, 1]
. - The fourth diagonal starting from
mat[1][0]
includes the elements[2, 1]
. - The fifth diagonal starting from
mat[2][0]
includes the elements[1, 2, 3]
(already sorted).
The sorting algorithm provided will iterate through these diagonals and sort them. Let's focus on how this algorithm would sort the third diagonal [1, 2, 1]
as an example, as it's the longest and requires actual sorting:
-
We retrieve the dimensions of the matrix, which are
m = 3
for rows andn = 3
for columns. -
We iterate starting from
mat[0][2]
, excluding the last row and column to make sure we won't accessmat[3][3]
which is out of bounds. -
Now, we compare each element on this diagonal with the subsequent diagonal element:
- Compare
mat[0][2]
(which is1
) withmat[1][3]
(which doesn't exist, so we skip this step). - Compare
mat[1][2]
(which is2
) withmat[2][3]
(which doesn't exist, so we skip this step).
Following the above approach, it seems we don't make any swaps. However, since we have to iterate
m - 1
times, we will re-iterate and compare the elements within the matrix boundaries again. - Compare
-
Since we are not going out of bounds, we re-iterate over the matrix:
- Compare
mat[0][2]
(which is1
) withmat[1][2]
(which is2
). No swap needed since1
is less than2
. - Compare
mat[1][2]
(which is2
) withmat[2][2]
(which is1
). Swap needed since2
is greater than1
.
- Compare
-
After the necessary swap, our diagonal now looks like
[1, 1, 2]
, and it is sorted in ascending order.
If we repeat this process for all diagonals, the final sorted matrix will be:
1mat = [ 2 [3, 2, 1], 3 [2, 1, 2], 4 [1, 1, 2] 5]
Note that each diagonal is individually sorted, even if the matrix as a whole isn't.
However, the described algorithm is not efficient as it might require many iterations for larger matrices due to its similarity to bubble sort, which has a high time complexity. Also, this example is for a square matrix – the algorithm may not perform correctly for non-square matrices because it does not iterate through all possible starting cells of the diagonals. A more efficient approach would be to extract each diagonal, sort it, and then place it back into the matrix.
Solution Implementation
1class Solution:
2 def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
3 # Get the number of rows and columns in the matrix.
4 num_rows, num_cols = len(mat), len(mat[0])
5
6 # Only need to iterate up to the smallest dimension minus one
7 # since we start the comparison from the second-to-last diagonal.
8 for _ in range(min(num_rows, num_cols) - 1):
9 # Iterate through each element in the matrix except for the last row and column.
10 for row in range(num_rows - 1):
11 for col in range(num_cols - 1):
12 # Compare the current element with the element in the next diagonal position.
13 if mat[row][col] > mat[row + 1][col + 1]:
14 # Swap the elements if they are out of order.
15 mat[row][col], mat[row + 1][col + 1] = mat[row + 1][col + 1], mat[row][col]
16
17 # Return the sorted matrix.
18 return mat
19
1class Solution {
2
3 /**
4 * Sorts each diagonal of the given matrix independently, where a diagonal
5 * is defined from the top-left to the bottom-right corners.
6 *
7 * @param matrix The matrix to be sorted diagonally.
8 * @return The diagonally sorted matrix.
9 */
10 public int[][] diagonalSort(int[][] matrix) {
11 // Determine the number of rows and columns in the matrix
12 int numRows = matrix.length;
13 int numCols = matrix[0].length;
14
15 // Iterate over each element of the matrix except the last row and column
16 for (int k = 0; k < Math.min(numRows, numCols) - 1; ++k) {
17 for (int i = 0; i < numRows - 1; ++i) {
18 for (int j = 0; j < numCols - 1; ++j) {
19
20 // Compare and swap elements if current element is greater
21 // than the element in the next row and next column
22 if (matrix[i][j] > matrix[i + 1][j + 1]) {
23 // Swap elements using a temporary variable
24 int temp = matrix[i][j];
25 matrix[i][j] = matrix[i + 1][j + 1];
26 matrix[i + 1][j + 1] = temp;
27 }
28 }
29 }
30 }
31
32 // Return the sorted matrix
33 return matrix;
34 }
35}
36
1#include <vector>
2#include <algorithm> // For std::sort function
3
4class Solution {
5public:
6 std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>>& matrix) {
7 int rowCount = matrix.size(); // Number of rows in the matrix
8 int colCount = matrix[0].size(); // Number of columns in the matrix
9
10 // Sort each diagonal that starts from the first column
11 for (int row = 0; row < rowCount; ++row) {
12 sortDiagonal(matrix, row, 0, rowCount, colCount);
13 }
14
15 // Sort each diagonal that starts from the first row, except the first diagonal which is already sorted
16 for (int col = 1; col < colCount; ++col) {
17 sortDiagonal(matrix, 0, col, rowCount, colCount);
18 }
19
20 return matrix;
21 }
22
23private:
24 // Helper function to sort a single diagonal starting at (startRow, startCol)
25 void sortDiagonal(std::vector<std::vector<int>>& matrix, int startRow, int startCol, int rowCount, int colCount) {
26 int row = startRow;
27 int col = startCol;
28 std::vector<int> diagonalElements;
29
30 // Collect all elements of the diagonal
31 while (row < rowCount && col < colCount) {
32 diagonalElements.push_back(matrix[row][col]);
33 ++row;
34 ++col;
35 }
36
37 // Sort the collected diagonal elements
38 std::sort(diagonalElements.begin(), diagonalElements.end());
39
40 // Put the sorted elements back into their places on the diagonal
41 row = startRow;
42 col = startCol;
43 for (int element : diagonalElements) {
44 matrix[row][col] = element;
45 ++row;
46 ++col;
47 }
48 }
49};
50
1type Matrix = number[][];
2
3// This function sorts the matrix diagonally
4function diagonalSort(matrix: Matrix): Matrix {
5 const rowCount = matrix.length; // Number of rows in the matrix
6 const colCount = matrix[0].length; // Number of columns in the matrix
7
8 // Sort each diagonal that starts from the first column
9 for (let row = 0; row < rowCount; ++row) {
10 sortDiagonal(matrix, row, 0, rowCount, colCount);
11 }
12
13 // Sort each diagonal that starts from the first row,
14 // except for the first diagonal which is already sorted
15 for (let col = 1; col < colCount; ++col) {
16 sortDiagonal(matrix, 0, col, rowCount, colCount);
17 }
18
19 return matrix;
20}
21
22// Helper function that sorts a single diagonal
23// starting at (startRow, startCol)
24function sortDiagonal(matrix: Matrix, startRow: number, startCol: number, rowCount: number, colCount: number): void {
25 let row = startRow;
26 let col = startCol;
27 const diagonalElements: number[] = [];
28
29 // Collect all elements of the diagonal
30 while (row < rowCount && col < colCount) {
31 diagonalElements.push(matrix[row][col]);
32 ++row;
33 ++col;
34 }
35
36 // Sort the collected diagonal elements
37 diagonalElements.sort((a, b) => a - b);
38
39 // Put the sorted elements back into their places on the diagonal
40 row = startRow;
41 col = startCol;
42 for (const element of diagonalElements) {
43 matrix[row][col] = element;
44 ++row;
45 ++col;
46 }
47}
48
Time and Space Complexity
The provided code has a nested loop structure that iterates over the elements in the matrix in a specific pattern to sort the diagonals. Let's analyze both the time and space complexity:
Time Complexity
The outermost loop is controlled by min(m, n) - 1
, where m
is the number of rows and n
is the number of columns in the matrix. This loop will run for the minimum dimension - 1.
Inside the outer loop, there are two nested loops that each run m - 1
and n - 1
times respectively, iterating over the elements of the matrix.
The combined time complexity is the product of these factors, resulting in O((min(m, n) - 1) * (m - 1) * (n - 1))
.
Simplifying, we drop constants and lower-order terms to focus on the growth rates, which gives us a time complexity of O(min(m, n) * m * n)
.
Space Complexity
The space complexity of the code is O(1)
because there are no data structures being used that grow with the size of the input. The only extra space used here is for the loop variables and a couple of temporary variables for the swapping process.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.