Most Frequent Prime

Problem

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 namely: east, south-east, south, south-west, west, north-west, north, and north-east.
Select a path from them and append digits in this path to the number being formed by traveling in this direction.
Note that numbers are generated at every step, for example, if the digits along the path are 1, 9, 1, then there will be three numbers generated along the way: 1, 19, 191.

Return _the most frequent prime number greater than _10 out of all the numbers created by traversing the matrix or-1 if no such prime number exists. If there are multiple prime numbers with the highest frequency, then return thelargest among them.

Note: It is invalid to change the direction during the move.

Examples

Example 1


**![](https://assets.leetcode.com/uploads/2024/02/15/south)**

Input: mat = [[1,1],[9,9],[1,1]]
Output: 19
Explanation: 
From cell (0,0) there are 3 possible directions and the numbers greater than 10 which can be created in those directions are:
East: [11], South-East: [19], South: [19,191].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [19,191,19,11].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [99,91,91,91,91].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [91,91,99,91,91].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [11,19,191,19].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [11,19,19,191].
The most frequent prime number among all the created numbers is 19.

Example 2

Input: mat = [[7]]
Output: -1
Explanation: The only number which can be formed is 7. It is a prime number however it is not greater than 10, so return -1.

Example 3

Input: mat = [[9,7,8],[4,6,5],[2,8,6]]
Output: 97
Explanation: 
Numbers greater than 10 created from the cell (0,0) in all possible directions are: [97,978,96,966,94,942].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [78,75,76,768,74,79].
Numbers greater than 10 created from the cell (0,2) in all possible directions are: [85,856,86,862,87,879].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [46,465,48,42,49,47].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [65,66,68,62,64,69,67,68].
Numbers greater than 10 created from the cell (1,2) in all possible directions are: [56,58,56,564,57,58].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [28,286,24,249,26,268].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [86,82,84,86,867,85].
Numbers greater than 10 created from the cell (2,2) in all possible directions are: [68,682,66,669,65,658].
The most frequent prime number among all the created numbers is 97.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 6
1 <= mat[i][j] <= 9

Solution

Method 1 - Enumeration + Primality Check

Intuition

We can enumerate all possible numbers formed by moving in each of the 8 directions from every cell, collecting numbers at each step. For each number > 10, check if it is prime and count its frequency. Finally, return the largest prime with the highest frequency.

Approach

For each cell, for each direction, traverse and build numbers step by step, collecting all numbers > 10.
For each such number, check if it is prime (using a simple primality test).
Count the frequency of each prime number.
Return the largest prime with the highest frequency, or -1 if none.

Code

Java

import java.util.*;
class Solution {
    int[][] dirs = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
    public int mostFrequentPrime(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] d : dirs) {
                    int x = i, y = j, num = 0;
                    for (int step = 0; step < Math.max(m, n); step++) {
                        num = num * 10 + mat[x][y];
                        if (num > 10 && isPrime(num)) {
                            freq.put(num, freq.getOrDefault(num, 0) + 1);
                        }
                        x = (x + d[0] + m) % m;
                        y = (y + d[1] + n) % n;
                    }
                }
            }
        }
        int maxFreq = 0, ans = -1;
        for (int k : freq.keySet()) {
            if (freq.get(k) > maxFreq || (freq.get(k) == maxFreq && k > ans)) {
                maxFreq = freq.get(k);
                ans = k;
            }
        }
        return ans;
    }
    boolean isPrime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

Python

def mostFrequentPrime(mat):
    from collections import Counter
    m, n = len(mat), len(mat[0])
    dirs = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]
    freq = Counter()
    def is_prime(x):
        if x < 2: return False
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0: return False
        return True
    for i in range(m):
        for j in range(n):
            for dx, dy in dirs:
                x, y, num = i, j, 0
                for step in range(max(m, n)):
                    num = num * 10 + mat[x][y]
                    if num > 10 and is_prime(num):
                        freq[num] += 1
                    x = (x + dx) % m
                    y = (y + dy) % n
    if not freq:
        return -1
    max_freq = max(freq.values())
    return max([k for k, v in freq.items() if v == max_freq])

Complexity

⏰ Time complexity: O(m * n * d * L) — For each cell, direction, and step, with L = number of digits, d = 8 directions.
🧺 Space complexity: O(K) — For frequency map, K = number of distinct primes found.