Most frequent prime

Array Hash Table Math Matrix Counting Enumeration Number Theory

45.8% acceptance

Feb 25, 2026

101

You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers in the following way: There could be at most 8 paths from the cells. Select a path from them and append digits in this path to the number being formed by traveling in this direction. Numbers are generated at every step. Return the most frequent prime number greater than 10, or -1 if no such prime exists. If multiple primes have the highest frequency, return the largest.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn most_frequent_prime(mat: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashMap;
    let m = mat.len();
    let n = mat[0].len();
    let dirs = [(-1i32,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)];
    let mut freq: HashMap<i32,i32> = HashMap::new();
    let is_prime = |x: i32| -> bool {
      if x < 2 { return false; }
      if x == 2 { return true; }
      if x % 2 == 0 { return false; }
      let mut i = 3;
      while i * i <= x { if x % i == 0 { return false; } i += 2; }
      true
    };
    for r in 0..m {
      for c in 0..n {
        for &(dr, dc) in &dirs {
          let mut num = mat[r][c];
          let mut nr = r as i32 + dr;
          let mut nc = c as i32 + dc;
          while nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
            num = num * 10 + mat[nr as usize][nc as usize];
            if num > 10 && is_prime(num) { *freq.entry(num).or_insert(0) += 1; }
            nr += dr; nc += dc;
          }
        }
      }
    }
    if freq.is_empty() { return -1; }
    let max_freq = *freq.values().max().unwrap();
    *freq.iter().filter(|&(_, &v)| v == max_freq).map(|(k, _)| k).max().unwrap()
  }
}