Sort matrix by diagonals

Array Sorting Matrix

84.7% acceptance

Feb 25, 2026

508

102

You are given an n x n square matrix of integers grid. Return the matrix such that: The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order. The diagonals in the top-right triangle are sorted in non-decreasing order.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sort_matrix(mut grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = grid.len();
    // Process each diagonal (bottom-left triangle including main: sort descending)
    // Diagonal d: cells where row - col = d, d in 0..n
    for d in 0..n as i32 {
      let mut diag: Vec<i32> = Vec::new();
      let mut cells: Vec<(usize, usize)> = Vec::new();
      let mut r = d as usize;
      let mut c = 0;
      while r < n && c < n {
        diag.push(grid[r][c]);
        cells.push((r, c));
        r += 1; c += 1;
      }
      diag.sort_unstable_by(|a, b| b.cmp(a)); // descending
      for (k, (rr, cc)) in cells.iter().enumerate() { grid[*rr][*cc] = diag[k]; }
    }
    // Top-right triangle (col - row = d, d in 1..n): sort ascending
    for d in 1..n as i32 {
      let mut diag: Vec<i32> = Vec::new();
      let mut cells: Vec<(usize, usize)> = Vec::new();
      let mut r = 0;
      let mut c = d as usize;
      while r < n && c < n {
        diag.push(grid[r][c]);
        cells.push((r, c));
        r += 1; c += 1;
      }
      diag.sort_unstable(); // ascending
      for (k, (rr, cc)) in cells.iter().enumerate() { grid[*rr][*cc] = diag[k]; }
    }
    grid
  }
}