#1329

Medium

LeetCode Problem Workspace

Sort the Matrix Diagonally

Sort each diagonal of a matrix in ascending order, applying sorting and matrix traversal techniques.

Problem Statement

Given a matrix of integers, sort each diagonal in ascending order. A diagonal is defined as a set of matrix elements that start at either the topmost row or the leftmost column and move bottom-right. For instance, starting from mat[2][0] in a 6x3 matrix, the diagonal includes mat[2][0], mat[3][1], and mat[4][2].

You need to sort all such diagonals in ascending order and return the updated matrix. Ensure to handle matrices with varying dimensions, making sure no diagonal is left unsorted.

Examples

Example 1

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]]

Example details omitted.

Example 2

Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]

Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

Example details omitted.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution Approach

Extract Diagonals

First, identify and collect the elements of each diagonal. Start from the leftmost column and the topmost row to extract all diagonals. Use a map or dictionary to store values for each diagonal.

Sort Diagonals

Once the diagonals are collected, sort each diagonal individually. Since sorting is required, consider the time complexity and choose an optimal sorting algorithm based on the diagonal size.

Place Sorted Values Back

After sorting the diagonals, place the sorted values back into the respective positions in the matrix, ensuring the diagonals retain their original positions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting algorithm used. Sorting the diagonals individually will take O(k log k) time per diagonal, where k is the number of elements in the diagonal. The space complexity is O(m * n) due to the storage of diagonal values for sorting.

What Interviewers Usually Probe

Can the candidate identify the diagonals efficiently?
Do they choose the correct sorting technique for each diagonal?
Are they able to place the sorted values back into the matrix with minimal overhead?

Common Pitfalls or Variants

Common pitfalls

Incorrectly identifying or indexing diagonals, leading to misplaced values.
Forgetting to sort diagonals separately or applying sorting to the entire matrix.
Not handling edge cases like small matrices or diagonals with only one element.

Follow-up variants

Handle larger matrices with m, n up to 100.
Optimize space usage by avoiding storing entire diagonals when possible.
Implement diagonal sorting for non-square matrices.

FAQ

How can I sort matrix diagonals efficiently?

Focus on extracting the diagonals first, then sort them individually. Make sure to minimize the number of passes through the matrix by handling diagonals separately.

What is the time complexity of sorting matrix diagonals?

The time complexity depends on the sorting algorithm used for each diagonal, typically O(k log k), where k is the number of elements in each diagonal.

What if the matrix has non-square dimensions?

The algorithm works for non-square matrices by extracting diagonals starting from the topmost row and the leftmost column.

How can GhostInterview help with matrix problems?

GhostInterview breaks down the matrix traversal and sorting process into clear, digestible steps, ensuring efficient diagonal extraction and sorting.

What is the core pattern in 'Sort the Matrix Diagonally'?

The core pattern is 'Array plus Sorting', where you extract and sort diagonals individually before placing them back into the matrix.

terminal

Solution

Solution 1: Sorting

We can treat each diagonal of the matrix as an array, sort these arrays, and then fill the sorted elements back into the original matrix.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        g = [[] for _ in range(m + n)]
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                g[m - i + j].append(x)
        for e in g:
            e.sort(reverse=True)
        for i in range(m):
            for j in range(n):
                mat[i][j] = g[m - i + j].pop()
        return mat

Continue Practicing

#1337 the k weakest rows in a matrix #1030 matrix cells in distance order #1632 rank transform of a matrix