Get biggest three rhombus sums in a grid

Array Math Sorting Heap (Priority Queue) Matrix Prefix Sum

50.1% acceptance

Feb 25, 2026

235

530

You are given an m x n integer matrix grid. A rhombus sum is the sum of the elements on the border of a regular rhombus shape. Return the biggest three distinct rhombus sums in descending order. If there are fewer than three distinct values, return all of them.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeSet;

impl Solution {
  pub fn get_biggest_three(grid: Vec<Vec<i32>>) -> Vec<i32> {
    let m = grid.len();
    let n = grid[0].len();
    let mut top3: BTreeSet<i32> = BTreeSet::new();

    let mut add = |v: i32| {
      top3.insert(v);
      if top3.len() > 3 {
        let min = *top3.iter().next().unwrap();
        top3.remove(&min);
      }
    };

    for r in 0..m {
      for c in 0..n {
        // k=0: single cell
        add(grid[r][c]);
        // k >= 1
        for k in 1.. {
          if r < k || r + k >= m || c < k || c + k >= n { break; }
          let mut sum = 0i32;
          for i in 0..k {
            sum += grid[r - k + i][c + i];     // top to right (excl. right corner)
            sum += grid[r + i][c + k - i];     // right to bottom (excl. bottom corner)
            sum += grid[r + k - i][c - i];     // bottom to left (excl. left corner)
            sum += grid[r - i][c - k + i];     // left to top (excl. top corner)
          }
          add(sum);
        }
      }
    }

    let result: Vec<i32> = top3.into_iter().rev().collect();
    result
  }
}