Algorithms Problem Solving: Sort the Matrix Diagonally
TK
Posted on June 22, 2020
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
Resources
💖 💪 🙅 🚩
TK
Posted on June 22, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
algorithms Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal
June 17, 2020