DEV Community

Cover image for Algorithms Problem Solving: Sort the Matrix Diagonally
TK
TK

Posted on • Originally published at leandrotk.github.io

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]]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Resources

Discussion (0)