Diagonal traverse ii

Array Sorting Heap (Priority Queue)

58.3% acceptance

Feb 25, 2026

2298

159

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_diagonal_order(nums: Vec<Vec<i32>>) -> Vec<i32> {
    let mut diag: std::collections::HashMap<usize, Vec<i32>> = std::collections::HashMap::new();
    for (i, row) in nums.iter().enumerate() {
      for (j, &val) in row.iter().enumerate() {
        diag.entry(i + j).or_default().push(val);
      }
    }
    let max_diag = diag.keys().copied().max().unwrap_or(0);
    let mut result = vec![];
    for d in 0..=max_diag {
      if let Some(v) = diag.get(&d) {
        // elements on the same diagonal are added from bottom-left to top-right
        // i.e., larger i first (since we want bottom row first)
        for &val in v.iter().rev() {
          result.push(val);
        }
      }
    }
    result
  }
}