This post is part of the Algorithms Problem Solving series.
Problem description
This is the Sort the Matrix Diagonally problem. The description looks like this:
Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.
Examples
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]]
Solution
- get the diagonal of each column for the first row
- sort the diagonal and put back into the matrix diagonal
- get the diagonal of each row for the first column
- sort the diagonal and put back into the matrix diagonal
- return the matrix
def diagonal_sort(mat):
for column in range(len(mat[0]) - 1):
diagonal_list = []
col = column
for row in range(len(mat)):
diagonal_list.append(mat[row][col])
col += 1
if col >= len(mat[0]):
break
diagonal_list = sorted(diagonal_list)
col = column
for row in range(len(mat)):
mat[row][col] = diagonal_list[row]
col += 1
if col >= len(mat[0]):
break
for row in range(1, len(mat)):
diagonal_list = []
r = row
for column in range(len(mat[0])):
diagonal_list.append(mat[r][column])
r += 1
if r >= len(mat):
break
diagonal_list = sorted(diagonal_list)
r = row
for column in range(len(mat[0])):
mat[r][column] = diagonal_list[column]
r += 1
if r >= len(mat):
break
return mat