Posted on Jun 22, 2020 • Originally published at leandrotk.github.io

Algorithms Problem Solving: Sort the Matrix Diagonally

#algorithms #python #computerscience #interview

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