Skip to content

3748. Sort Matrix By Diagonals

Array Sorting Matrix

Problem - Sort Matrix By Diagonals

Medium

You are given an n x n square matrix of integers grid. Return the matrix such that:

  • The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order.
  • The diagonals in the top-right triangle are sorted in non-decreasing order.

 

Example 1:

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

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

Explanation:

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

  • [1, 8, 6] becomes [8, 6, 1].
  • [9, 5] and [4] remain unchanged.

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

  • [7, 2] becomes [2, 7].
  • [3] remains unchanged.

Example 2:

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

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

Explanation:

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]]

Explanation:

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

Solutions

 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
31
32
33
34
35
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
            temp = []
            while i < n and j < n:
                temp.append(grid[i][j])
                i += 1
                j += 1
            temp.sort()

            i, j = k, 0
            while i < n and j < n:
                grid[i][j] = temp.pop()
                i += 1
                j += 1

        for k in range(n - 2, 0, -1):
            i, j = k, n - 1
            temp = []
            while i >= 0 and j >= 0:
                temp.append(grid[i][j])
                i -= 1
                j -= 1
            temp.sort()

            i, j = k, n - 1
            while i >= 0 and j >= 0:
                grid[i][j] = temp.pop()
                i -= 1
                j -= 1

        return grid

Submission Stats:

  • Runtime: 3 ms (98.62%)
  • Memory: 18 MB (30.52%)