Sort the matrix diagonally

Array Sorting Matrix

83.2% acceptance

Feb 25, 2026

3570

239

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2]. Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn diagonal_sort(mut mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = mat.len();
    let n = mat[0].len();
    use std::collections::HashMap;
    let mut diags: HashMap<i32, Vec<i32>> = HashMap::new();
    for i in 0..m {
      for j in 0..n {
        diags.entry(i as i32 - j as i32).or_default().push(mat[i][j]);
      }
    }
    for v in diags.values_mut() { v.sort(); }
    // Track position per diagonal
    let mut idx: HashMap<i32, usize> = HashMap::new();
    for i in 0..m {
      for j in 0..n {
        let key = i as i32 - j as i32;
        let pos = idx.entry(key).or_insert(0);
        mat[i][j] = diags[&key][*pos];
        *pos += 1;
      }
    }
    mat
  }
}