Sort the values on each diagonal of a matrix independently, then rebuild the matrix with those sorted diagonals.
Problem
Given an matrix, sort the elements on every diagonal that runs from the top-left to the bottom-right independently.
For each diagonal, collect all values on that diagonal, sort them in non-decreasing order, and place them back onto the same diagonal positions.
Return the transformed matrix.
A diagonal is identified by the cells that share the same value of row - column.
Goal
Produce a new matrix arrangement where every top-left to bottom-right diagonal is individually sorted in ascending order.
Input Format
- A 2D integer matrix
matwithmrows andncolumns. - Diagonals are the sets of cells with equal
row - column. - Values may be repeated.
Output Format
- Return the matrix after sorting each diagonal independently in ascending order.
Constraints
- The matrix contains integers.
- The exact bounds are unspecified here; assume standard interview-sized inputs.
- You may modify the matrix in place or return a new matrix.
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
Each top-left to bottom-right diagonal is sorted independently. For example, the main diagonal [3,2,1] becomes [1,2,3].
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,31,36,50,66,24],[84,28,75,33,55,68]]
Explanation
This illustrates sorting every diagonal independently and placing the sorted values back onto the same diagonal positions.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.