DEV Community

loading...
Cover image for Algorithms Problem Solving: Sort the Matrix Diagonally

Algorithms Problem Solving: Sort the Matrix Diagonally

TK
Sharing knowledge https://leandrotk.github.io
Originally published at leandrotk.github.io ・2 min read

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)