LeetCode Solutions Blog

Sort Matrix by Diagonals

Difficulty: Medium

Problem Description

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.

Key Insights

The matrix can be divided into two triangles: bottom-left and top-right.
Each diagonal can be identified by its starting point in the matrix.
We can collect values from each diagonal, sort them accordingly, and then place them back into their respective positions in the matrix.

Space and Time Complexity

Time Complexity: O(n^2 log n) - Sorting the diagonals takes logarithmic time relative to the number of elements in each diagonal. Space Complexity: O(n) - We need space to store diagonal values temporarily.

Solution

Identify and store the elements of each diagonal in both the bottom-left and top-right triangles.
Sort the bottom-left diagonals in non-increasing order and the top-right diagonals in non-decreasing order.
Reinsert the sorted values back into their original positions in the matrix.

Code Solutions

def sortMatrixDiagonally(grid):
    n = len(grid)
    # Dictionary to hold diagonals
    diagonals = {}
    
    # Collect bottom-left diagonals
    for i in range(n):
        for j in range(n):
            diag_id = i + j
            if diag_id not in diagonals:
                diagonals[diag_id] = []
            diagonals[diag_id].append(grid[i][j])
    
    # Sort bottom-left diagonals in non-increasing order
    for key in diagonals:
        diagonals[key].sort(reverse=True)
    
    # Reinsert sorted values back into the grid
    for i in range(n):
        for j in range(n):
            diag_id = i + j
            grid[i][j] = diagonals[diag_id].pop()
    
    # Collect top-right diagonals
    diagonals = {}
    for i in range(n):
        for j in range(n):
            diag_id = j - i
            if diag_id not in diagonals:
                diagonals[diag_id] = []
            diagonals[diag_id].append(grid[i][j])
    
    # Sort top-right diagonals in non-decreasing order
    for key in diagonals:
        diagonals[key].sort()
    
    # Reinsert sorted values back into the grid
    for i in range(n):
        for j in range(n):
            diag_id = j - i
            grid[i][j] = diagonals[diag_id].pop(0)
    
    return grid