Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every top-left-to-bottom-right diagonal can be sorted independently. Diagonals starting in the first column, including the main diagonal, need nonincreasing order; those starting in the top row after the first column need nondecreasing order.

Approach

Python groups all cells by column - row, sorts buckets with nonpositive keys ascending and positive keys descending, then fills the matrix in row-major order by popping each bucket's last value. Along each diagonal this visits cells from top-left to bottom-right.

JavaScript instead gathers, sorts, and writes back one diagonal at a time: first all starts in the first column, then the remaining starts in the top row. Both versions sort in the reverse of the desired output order because values are removed from the end. Thus ascending lists produce nonincreasing lower-left diagonals, and descending lists produce nondecreasing upper-right diagonals. Return the modified matrix; each diagonal retains exactly its original values.

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        d = defaultdict(list)
        for i in range(n):
            for j in range(n):
                d[j - i].append(grid[i][j])

        for k in d:
            if k <= 0:
                d[k].sort()
            else:
                d[k].sort(reverse = True)

        for i in range(n):
            for j in range(n):
                grid[i][j] = d[j - i].pop()

        return grid

Complexity analysis

Let n be the square-matrix side length. Both versions take O(n^2 log(n+1)) time, including collection and write-back. Python uses O(n^2) auxiliary space for all diagonal buckets. JavaScript uses O(n) auxiliary space for one diagonal and its sort workspace. Both modify the input matrix.