Sort The Matrix Diagonally - Leetcode Solution

Problem Statement:

Given a matrix of integers mat, sort each diagonal in ascending order and return the resulting matrix.

Example: Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Explanation:

The input matrix is:

3   3   1   1
2   2   1   2
1   1   1   2

We need to sort all the diagonals of the matrix in ascending order. The diagonal from (0,0) to (2,2) contains {3, 2, 1} which should be sorted in ascending order - {1, 2, 3}. The diagonal from (0,1) to (2,3) contains {3, 2, 1, 2} which should be sorted in ascending order - {1, 2, 2, 3}. The diagonal from (1,0) to (2,1) contains {2, 1} which should be sorted in ascending order - {1, 2}. The diagonal from (2,0) to (2,2) contains {1, 1, 1} which should be sorted in ascending order - {1, 1, 1}. The diagonal from (1,3) to (2,3) contains {2} which should be sorted in ascending order - {2}. The result is matrix:

1   1   1   1
1   2   2   2
1   2   3   3

Solution:

To solve this problem, we can traverse each diagonal of the matrix starting from the top-left corner. We can keep a hashmap of all the diagonals and their elements. We can then sort each diagonal and update the matrix accordingly.

First, we need to traverse all the diagonals of the matrix starting from the top-left corner. There are a total of m+n-1 diagonals that need to be traversed, where m and n are the number of rows and columns of the matrix respectively.

For each diagonal, we can compute its index using the row and column index of the first element of the diagonal. We can then add the element to the hashmap of that diagonal.

After all the elements have been added to their respective diagonals, we can sort each diagonal in ascending order and update the matrix accordingly.

We can then return the sorted matrix.

Here is the Python implementation of the solution:

def diagonalSort(mat): m, n = len(mat), len(mat[0]) # Get dimensions of matrix diag_map = {} # Create HashMap to store each diagonal

# Traverse all diagonals starting from top-left corner
for i in range(m):
    for j in range(n):
        if (i - j) not in diag_map:
            diag_map[i - j] = []
        diag_map[i - j].append(mat[i][j])

# Sort each diagonal in ascending order
for k in diag_map:
    diag_map[k].sort()

# Update the matrix with sorted elements
for i in range(m):
    for j in range(n):
        mat[i][j] = diag_map[i - j].pop(0)

return mat

Time Complexity:

The time complexity of the above solution is O(mnlogd) where d = min(m,n) is the length of the longest diagonal. The time complexity is dominated by sorting each diagonal.

Space Complexity:

The space complexity of the above solution is O(mn) to store the hashmap of all the diagonals and their elements.

Overall, this solution provides an efficient way to sort each diagonal of the matrix in ascending order.

1