Practice/Meta/Leetcode 1329. Sort the Matrix Diagonally

Leetcode 1329. Sort the Matrix Diagonally

CodingOptional

Problem

You are given a rectangular matrix of integers with m rows and n columns. Your task is to sort each diagonal that runs from the top-left toward the bottom-right direction independently, arranging the values in ascending order. After sorting all diagonals, return the modified matrix.

A diagonal in this context starts from any cell in the first row or first column and proceeds diagonally downward and to the right until reaching the matrix boundary.

Requirements

1. Sort each top-left to bottom-right diagonal independently in ascending order
2. Return the modified matrix with all diagonals sorted
3. Preserve the matrix dimensions (m × n remains unchanged)
4. Handle matrices of any rectangular shape (including square matrices)

Constraints

• 1 ≤ m, n ≤ 100 (matrix dimensions)
• 1 ≤ mat[i][j] ≤ 100 (cell values)
• Time complexity should be O(m × n × log(min(m, n)))
• Space complexity should be O(min(m, n)) for storing diagonal elements

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

• Diagonal starting at (0,0): [3,2,1] becomes [1,2,3]
• Diagonal starting at (0,1): [3,2,1] becomes [1,2,3]
• Diagonal starting at (0,2): [1,1,1] becomes [1,1,1]
• Diagonal starting at (0,3): [1,2,2] becomes [1,2,2]
• Diagonal starting at (1,0): [2,1] becomes [1,2]
• Diagonal starting at (2,0): [1] remains [1] `

Example 2:

Input: mat = [[11,25,66,1,69,7]] Output: [[11,25,66,1,69,7]] Explanation: Single-row matrix has all elements on separate diagonals, so no changes occur.

Example 3:

` Input: mat = [[5,6],[7,8]] Output: [[5,6],[7,8]] Explanation:

• Diagonal (0,0) to (1,1): [5,8] stays [5,8]
• Diagonal (0,1): [6] stays [6]
• Diagonal (1,0): [7] stays [7] `