3446. Sort Matrix by Diagonals
Approach
Extract each diagonal; sort ascending (lower-left) or descending (upper-right); re-insert.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.
// Approach: Extract each diagonal; sort ascending (lower-left) or descending (upper-right); re-insert.
// Time: O(mn log(min(m,n))) Space: O(mn)
public class Solution
{
public int[][] SortMatrix(int[][] grid)
{
int n = grid.Length;
// Sort the diagonals starting from the last column and moving upwards
for (int startRow = n - 2; startRow >= 0; --startRow)
{
int i = startRow, j = 0;
List<int> diagonalElements = new List<int>();
// Collect elements of the current diagonal
while (i < n && j < n)
{
diagonalElements.Add(grid[i][j]);
i++;
j++;
}
// Sort the collected diagonal elements
diagonalElements.Sort();
// Place the sorted elements back into the grid
for (int elementIndex = 0; elementIndex < diagonalElements.Count; elementIndex++)
grid[--i][--j] = diagonalElements[elementIndex];
}
// Sort the diagonals starting from the last row and moving to the first row
for (int startColumn = n - 2; startColumn > 0; --startColumn)
{
int i = startColumn, j = n - 1;
List<int> diagonalElements = new List<int>();
// Collect elements of the current diagonal
while (i >= 0 && j >= 0)
{
diagonalElements.Add(grid[i][j]);
i--;
j--;
}
// Sort the collected diagonal elements
diagonalElements.Sort();
// Place the sorted elements back into the grid
for (int elementIndex = 0; elementIndex < diagonalElements.Count; elementIndex++)
grid[++i][++j] = diagonalElements[elementIndex];
}
// Return the sorted grid
return grid;
}
}