How do you solve Sort the Matrix Diagonally on LeetCode?

Sort the Matrix Diagonally (LeetCode #1329) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n² log n) time complexity and O(n) space complexity. Key insight: Diagonals can be indexed by the sum of their coordinates (i + j).

What is the brute force solution for Sort the Matrix Diagonally?

The brute force approach for Sort the Matrix Diagonally is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves extracting each diagonal from the matrix, sorting it, and then placing the sorted values back into their respective diagonal positions. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n² log n).

What algorithm or data structure is used to solve Sort the Matrix Diagonally?

Sort the Matrix Diagonally uses the following concepts: Array, Sorting, Matrix. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Sort the Matrix Diagonally?

Clarify the problem statement and constraints before diving into coding. Think about edge cases, such as very small matrices. Discuss your thought process and approach with the interviewer.

What are common mistakes when solving Sort the Matrix Diagonally?

Not correctly identifying diagonal indices. Failing to sort the diagonals before placing them back.

#1329

Sort the Matrix Diagonally

Medium

ArraySortingMatrixHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n² log n)
Space	O(n)	O(n)

💡

Intuition

Time O(n² log n)Space O(n)

The optimal solution leverages the same diagonal extraction and sorting concept but uses a more efficient way to manage the sorting and placement of values, minimizing the number of operations.

⚙️

Algorithm

3 steps

1Step 1: Use a map to store the diagonals as before.
2Step 2: For each diagonal, sort the values directly in-place.
3Step 3: Instead of popping values, use an index to track where to place sorted values back into the matrix.

solution.py22 lines

1# Full working Python code
2from collections import defaultdict
3
4def diagonalSort(mat):
5    diagonals = defaultdict(list)
6    m, n = len(mat), len(mat[0])
7
8    # Step 1: Collect values in diagonals
9    for i in range(m):
10        for j in range(n):
11            diagonals[i + j].append(mat[i][j])
12
13    # Step 2: Sort each diagonal
14    for key in diagonals:
15        diagonals[key].sort()
16
17    # Step 3: Place sorted values back
18    for i in range(m):
19        for j in range(n):
20            mat[i][j] = diagonals[i + j][j - (i - (i + j) % n)]
21
22    return mat

ℹ

Complexity note: The time complexity remains O(n² log n) due to sorting, but the in-place placement of sorted values reduces the overhead of list operations. The space complexity is O(n) for storing diagonal values.

1Diagonals can be indexed by the sum of their coordinates (i + j).
2Sorting is necessary to achieve the desired order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.