Home

Sort the Matrix Diagonally

Matrix Photo by Ivan Bandura

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

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

Patreon Become a Patron Coffee icon Buy me a coffee