#3446

Medium

LeetCode Problem Workspace

Sort Matrix by Diagonals

Sort Matrix by Diagonals groups cells by diagonal, then sorts bottom-left diagonals descending and top-right diagonals ascending before writing back.

array sorting matrix

Problem Statement

You are given a square integer matrix. Your job is to reorder every top-left to bottom-right diagonal, but not all diagonals use the same direction. Diagonals that belong to the bottom-left part of the matrix, including the main diagonal, must end up in non-increasing order, while diagonals in the top-right part must end up in non-decreasing order.

The easiest way to view this problem is that cells with the same row minus column belong to one diagonal. After sorting each diagonal with its required direction, place the numbers back into their original diagonal positions and return the updated matrix. Single-cell diagonals stay unchanged because they are already sorted.

Examples

Example 1

Input: grid = [[1,7,3],[9,8,2],[4,5,6]]

Output: [[8,2,3],[9,6,7],[4,5,1]]

The diagonals with a black arrow (bottom-left triangle) should be sorted in non-increasing order: The diagonals with a blue arrow (top-right triangle) should be sorted in non-decreasing order:

Example 2

Input: grid = [[0,1],[1,2]]

Output: [[2,1],[1,0]]

The diagonals with a black arrow must be non-increasing, so [0, 2] is changed to [2, 0] . The other diagonals are already in the correct order.

Example 3

Input: grid = [[1]]

Output: [[1]]

Diagonals with exactly one element are already in order, so no changes are needed.

Constraints

grid.length == grid[i].length == n
1 <= n <= 10
-105 <= grid[i][j] <= 105

Solution Approach

Group cells by diagonal key

Cells on the same top-left to bottom-right diagonal share the same value of row minus column. Traverse the matrix once, push each value into a bucket for that key, and separate whether that diagonal should be descending or ascending based on where it begins. This keeps the matrix logic simple and avoids trying to sort in place across overlapping positions.

Sort each diagonal in the correct direction

For Sort Matrix by Diagonals, the failure mode is applying one sorting rule to every bucket. Diagonals from the left edge, which represent the bottom-left triangle and the main diagonal, must be sorted in descending order. Diagonals from the top edge, excluding the main diagonal, must be sorted in ascending order. Because n is small, a straightforward sort for every bucket is enough.

Write values back along each diagonal

Traverse the matrix again in the same row-major order and refill each cell from its diagonal bucket. A practical trick is to sort each bucket once, then pop from the front with an index pointer or pop from the end after choosing the reversed order carefully. This rebuild step guarantees each diagonal is internally sorted without disturbing any other diagonal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

If the matrix is n by n, collecting all values takes O(n^2). Sorting every diagonal costs the sum of k log k over all diagonals, which is at most O(n^2 log n) because no diagonal is longer than n. Storing the diagonal buckets uses O(n^2) extra space in the direct approach.

What Interviewers Usually Probe

They expect you to notice that row minus column uniquely identifies a top-left to bottom-right diagonal.
They want you to separate the main diagonal plus bottom-left triangle from the top-right triangle because the sort directions differ.
They are checking whether you can rebuild the matrix cleanly after sorting each diagonal instead of forcing a brittle in-place swap process.

Common Pitfalls or Variants

Common pitfalls

Using the same ascending order for every diagonal, which breaks the main diagonal and lower-left diagonals.
Keying diagonals incorrectly with row plus column, which groups anti-diagonals instead of the required diagonals.
Starting diagonals from every cell and sorting duplicates multiple times, which adds bugs and unnecessary work.

Follow-up variants

Sort all diagonals in ascending order only, which removes the need to branch on diagonal position.
Apply the same diagonal-bucketing idea to rectangular matrices where lengths differ across diagonals.
Sort anti-diagonals instead of main-direction diagonals, which changes the grouping key from row minus column to row plus column.

FAQ

What is the main pattern in Sort Matrix by Diagonals?

The core pattern is array plus sorting on diagonal buckets. Group cells by row minus column, sort each bucket with the correct direction, then write the values back into the matrix.

Why use row minus column for this problem?

In a square matrix, every cell on the same top-left to bottom-right diagonal has the same row minus column value. That makes it the natural key for collecting and sorting each diagonal independently.

How do I decide whether a diagonal is ascending or descending?

If the diagonal belongs to the main diagonal or starts from the left edge, it should be non-increasing. If it starts from the top edge and is to the right of the main diagonal, it should be non-decreasing.

Can Sort Matrix by Diagonals be done in place without extra storage?

You can try, but it becomes much harder because each diagonal needs its own ordered sequence before reassignment. Using extra buckets is cleaner, less error-prone, and fully acceptable for the given constraints.

What makes this problem Medium instead of Easy?

The tricky part is not collecting diagonals. The real challenge is handling two sorting directions correctly and rebuilding the matrix without mixing top-right diagonals with the main and bottom-left diagonals.

terminal

Solution

Solution 1: Simulation + Sorting

We can simulate the diagonal sorting process as described in the problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        for k in range(n - 2, -1, -1):
            i, j = k, 0
            t = []
            while i < n and j < n:
                t.append(grid[i][j])
                i += 1
                j += 1
            t.sort()
            i, j = k, 0
            while i < n and j < n:
                grid[i][j] = t.pop()
                i += 1
                j += 1
        for k in range(n - 2, 0, -1):
            i, j = k, n - 1
            t = []
            while i >= 0 and j >= 0:
                t.append(grid[i][j])
                i -= 1
                j -= 1
            t.sort()
            i, j = k, n - 1
            while i >= 0 and j >= 0:
                grid[i][j] = t.pop()
                i -= 1
                j -= 1
        return grid

Continue Practicing

#3462 maximum sum with at most k elements #3567 minimum absolute difference in sliding submatrix #2931 maximum spending after buying items