Algorithms Problem Solving: Sort the Matrix Diagonally

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

• Learning Python: From Zero to Hero
• Algorithms Problem Solving Series
• Stack Data Structure
• Queue Data Structure
• Linked List
• Tree Data Structure