Sort each diagonal of a matrix independently in non-decreasing order.
Given an matrix, reorder the elements on every diagonal so that values along the same top-left to bottom-right diagonal appear in non-decreasing order.
A diagonal is identified by cells that share the same value of . After processing, each diagonal should contain exactly the same multiset of values as before, but sorted from the top-left end toward the bottom-right end.
Input Format
- A 2D integer matrix
matof sizem x n. - You should treat the matrix as already loaded in memory.
Output Format
- Return a new matrix, or modify the matrix in place, where every top-left to bottom-right diagonal is sorted in non-decreasing order.
Constraints
- Matrix values are integers
- Each diagonal must preserve its original elements
- The exact official constraints are not provided here
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,27,31,36,50,66],[84,28,75,33,55,68]]
Explanation
This is a standard diagonal-sorting example: each diagonal is collected, sorted, and written back in 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.