How can I sort matrix diagonals efficiently?

Focus on extracting the diagonals first, then sort them individually. Make sure to minimize the number of passes through the matrix by handling diagonals separately.

What is the time complexity of sorting matrix diagonals?

The time complexity depends on the sorting algorithm used for each diagonal, typically O(k log k), where k is the number of elements in each diagonal.

What if the matrix has non-square dimensions?

The algorithm works for non-square matrices by extracting diagonals starting from the topmost row and the leftmost column.

How can GhostInterview help with matrix problems?

GhostInterview breaks down the matrix traversal and sorting process into clear, digestible steps, ensuring efficient diagonal extraction and sorting.

What is the core pattern in 'Sort the Matrix Diagonally'?

The core pattern is 'Array plus Sorting', where you extract and sort diagonals individually before placing them back into the matrix.

#1329

Medium

auto_awesome数组·排序

LeetCode 题解工作台

将矩阵按对角线排序

矩阵对角线是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的矩阵对角线将会经过 mat[2][0] 、 mat[3][1] 和 mat[4][2] 。给你一个 m * n 的整数矩阵…

数组排序矩阵

题目描述

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

示例 1：

输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

示例 2：

输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

lightbulb

解题思路

方法一：排序

我们可以将矩阵中的每条对角线看作一个数组，然后对这些数组进行排序，最后再将排序后的元素填回原矩阵中。

具体地，我们记矩阵的行数为 $m$ ，列数为 $n$ 。由于同一条对角线上的任意两个元素 $(i_1, j_1)$ 和 $(i_2, j_2)$ 满足 $j_1 - i_1 = j_2 - i_2$ ，我们可以根据 $j - i$ 的值来确定每条对角线。为了保证值为正数，我们加上一个偏移量 $m$ ，即 $m - i + j$ 。

最后，我们将每条对角线上的元素排序后填回原矩阵中即可。

时间复杂度 $O(m \times n \times \log \min(m, n))$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        g = [[] for _ in range(m + n)]
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                g[m - i + j].append(x)
        for e in g:
            e.sort(reverse=True)
        for i in range(m):
            for j in range(n):
                mat[i][j] = g[m - i + j].pop()
        return mat

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the diagonals efficiently?
question_mark
Do they choose the correct sorting technique for each diagonal?
question_mark
Are they able to place the sorted values back into the matrix with minimal overhead?

warning

常见陷阱

外企场景

error
Incorrectly identifying or indexing diagonals, leading to misplaced values.
error
Forgetting to sort diagonals separately or applying sorting to the entire matrix.
error
Not handling edge cases like small matrices or diagonals with only one element.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle larger matrices with m, n up to 100.
arrow_right_alt
Optimize space usage by avoiding storing entire diagonals when possible.
arrow_right_alt
Implement diagonal sorting for non-square matrices.

help

常见问题

外企场景

继续练习

#1337 矩阵中战斗力最弱的 K 行 #1030 距离顺序排列矩阵单元格 #1632 矩阵转换后的排名