# Most Frequent Prime
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-frequent-prime)
Canonical: https://scaleengineer.com/dsa/problems/most-frequent-prime
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Hash Table, Matrix
---
## Problem
You are given a `m x n` **0-indexed** 2Dmatrix `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 the **largest** among them._

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

**Example 1:**

**![](https://assets.glich.co/dsa/most-frequent-prime/image0.jpg)** 

 
**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`

# Approaches
## Brute-Force Traversal with Trial Division
This approach directly simulates the process described in the problem. It iterates through every cell of the matrix, and from each cell, it explores all 8 possible directions to form numbers. For each number generated that is greater than 10, it performs a primality test using trial division. The frequencies of the prime numbers found are stored in a hash map. Finally, it scans the map to find the most frequent prime, resolving ties by choosing the largest one.
**Time:** O(M * N * L * sqrt(V)), where `M` and `N` are the dimensions of the matrix, `L = max(M, N)` is the maximum path length, and `V` is the maximum possible number formed (up to `10^L`). Given the constraints `M, N <= 6`, this is feasible. · **Space:** O(M * N * L) to store the frequencies of the prime numbers. In the worst case, every number generated could be a unique prime.
**Pros:** Simple to understand and implement.; Low memory usage compared to pre-computation methods, as it doesn't require a large sieve array.
**Cons:** Inefficient due to repeated primality tests for the same numbers and the slow trial division method.; For larger constraints, this approach would be too slow.
### Explanation
The core of this method is a nested loop structure. The outer loops iterate over each cell `(r, c)` of the `m x n` matrix. For each cell, an inner loop iterates through 8 predefined directions (North, North-East, East, etc.). These directions can be represented by `dx` and `dy` arrays, e.g., `dx = {-1, -1, -1, 0, 0, 1, 1, 1}` and `dy = {-1, 0, 1, -1, 1, -1, 0, 1}`.

For each starting cell and direction, we build numbers by traversing along the path. We start with the digit at the current cell and append digits from subsequent cells in the chosen direction. At each step of the traversal, a new number is formed. If this number is greater than 10, we check if it's prime using a helper function `isPrime(num)`.

The `isPrime(num)` function implements the trial division method: it checks for divisibility of `num` by integers from 2 up to `sqrt(num)`. If no divisors are found, the number is prime. A `HashMap<Integer, Integer>` is used to store the counts of all valid prime numbers encountered.

After checking all paths from all cells, we iterate through the frequency map to determine the prime number with the highest frequency. If there's a tie, the largest prime number is selected. If no prime numbers greater than 10 were found, we return -1.

```java
class Solution {
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public int mostFrequentPrime(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        Map<Integer, Integer> primeCounts = new HashMap<>();
        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 8; k++) {
                    int currentNum = 0;
                    int r = i;
                    int c = j;
                    while (r >= 0 && r < m && c >= 0 && c < n) {
                        currentNum = currentNum * 10 + mat[r][c];
                        if (currentNum > 10 && isPrime(currentNum)) {
                            primeCounts.put(currentNum, primeCounts.getOrDefault(currentNum, 0) + 1);
                        }
                        r += dr[k];
                        c += dc[k];
                    }
                }
            }
        }

        int maxFreq = 0;
        int result = -1;
        for (Map.Entry<Integer, Integer> entry : primeCounts.entrySet()) {
            int prime = entry.getKey();
            int freq = entry.getValue();
            if (freq > maxFreq) {
                maxFreq = freq;
                result = prime;
            } else if (freq == maxFreq) {
                result = Math.max(result, prime);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize a `HashMap<Integer, Integer> freqMap`.
*   Define 8 directions `(dr, dc)`.
*   For each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`:
    *   For each direction `d` from 0 to 7:
        *   Initialize `currentNum = 0`, `currR = r`, `currC = c`.
        *   While `(currR, currC)` is within matrix bounds:
            *   `currentNum = currentNum * 10 + mat[currR][currC]`.
            *   If `currentNum > 10` and `isPrime(currentNum)`:
                *   `freqMap.put(currentNum, freqMap.getOrDefault(currentNum, 0) + 1)`.
            *   Update `currR += dr[d]`, `currC += dc[d]`.
*   Find the most frequent prime from `freqMap`.
*   Return the result or -1.

## Traversal with Pre-computed Primes using Sieve
This approach improves upon the brute-force method by optimizing the primality test. Before starting the traversal of the matrix, it pre-computes all prime numbers up to the maximum possible value that can be formed from the matrix. The Sieve of Eratosthenes is an efficient algorithm for this purpose. With the primes pre-computed, checking if a number is prime becomes a constant time lookup. The rest of the logic for traversing the matrix and counting frequencies remains the same.
**Time:** O(V_max * log(log(V_max)) + M * N * L), where `V_max` is the upper bound for the sieve (e.g., `10^6`), and `M, N, L` are the matrix dimensions and max path length. The sieve part dominates, but it's a one-time cost. · **Space:** O(V_max + M * N * L). The space is dominated by the `V_max` size of the sieve array, where `V_max` is the maximum possible number.
**Pros:** Much faster than the trial division approach due to O(1) primality checks after the initial setup.; Very efficient for the given constraints.
**Cons:** Higher memory usage due to the sieve array. This could be a problem if the maximum possible number was much larger.
### Explanation
First, we determine the maximum possible number that can be generated. Given the matrix dimensions `m, n <= 6`, the longest number will have at most 6 digits. The maximum value is less than `1,000,000`. We create a boolean array, say `isNotPrime`, of size `1,000,001` and use the Sieve of Eratosthenes to mark all non-prime numbers. This pre-computation step is done only once.

The Sieve algorithm works by iterating from 2 up to the square root of the limit. For each prime number `p` it finds, it marks all multiples of `p` (i.e., `2p, 3p, 4p, ...`) as not prime.

After the sieve is built, the main logic proceeds as in the first approach: iterate through all cells, all 8 directions, and build numbers along each path. For each generated number `currentNum` greater than 10, we now perform a primality test in `O(1)` time by checking `!isNotPrime[currentNum]`. If the number is prime, we update its frequency in a hash map.

Finally, we analyze the frequency map to find the most frequent prime, handling ties by choosing the larger value.

```java
class Solution {
    private static final int MAX_VAL = 1000001; // Max number can be 999999
    private static boolean[] isNotPrime = new boolean[MAX_VAL];

    // Static block to pre-compute primes using Sieve
    static {
        isNotPrime[0] = isNotPrime[1] = true;
        for (int i = 2; i * i < MAX_VAL; i++) {
            if (!isNotPrime[i]) {
                for (int j = i * i; j < MAX_VAL; j += i) {
                    isNotPrime[j] = true;
                }
            }
        }
    }

    public int mostFrequentPrime(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        Map<Integer, Integer> primeCounts = new HashMap<>();
        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 8; k++) {
                    int currentNum = 0;
                    int r = i;
                    int c = j;
                    while (r >= 0 && r < m && c >= 0 && c < n) {
                        currentNum = currentNum * 10 + mat[r][c];
                        if (currentNum > 10) {
                            if (!isNotPrime[currentNum]) {
                                primeCounts.put(currentNum, primeCounts.getOrDefault(currentNum, 0) + 1);
                            }
                        }
                        r += dr[k];
                        c += dc[k];
                    }
                }
            }
        }

        int maxFreq = 0;
        int result = -1;
        for (Map.Entry<Integer, Integer> entry : primeCounts.entrySet()) {
            int prime = entry.getKey();
            int freq = entry.getValue();
            if (freq > maxFreq) {
                maxFreq = freq;
                result = prime;
            } else if (freq == maxFreq) {
                result = Math.max(result, prime);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Determine `MAX_VAL` (e.g., `1,000,000`).
*   Create a boolean array `isNotPrime` of size `MAX_VAL`.
*   Run Sieve of Eratosthenes on `isNotPrime` to mark non-prime numbers.
*   Initialize a `HashMap<Integer, Integer> freqMap`.
*   For each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`:
    *   For each of the 8 directions `d`:
        *   Traverse the path, building `currentNum`.
        *   If `currentNum > 10` and `!isNotPrime[currentNum]`:
            *   Update `freqMap`.
*   Find the most frequent prime from `freqMap`.
*   Return the result or -1.

# Solutions
### Java

```java
class Solution {
public
  int mostFrequentPrime(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int a = -1; a <= 1; ++a) {
          for (int b = -1; b <= 1; ++b) {
            if (a == 0 && b == 0) {
              continue;
            }
            int x = i + a, y = j + b, v = mat[i][j];
            while (x >= 0 && x < m && y >= 0 && y < n) {
              v = v * 10 + mat[x][y];
              if (isPrime(v)) {
                cnt.merge(v, 1, Integer : : sum);
              }
              x += a;
              y += b;
            }
          }
        }
      }
    }
    int ans = -1, mx = 0;
    for (var e : cnt.entrySet()) {
      int v = e.getKey(), x = e.getValue();
      if (mx < x || (mx == x && ans < v)) {
        mx = x;
        ans = v;
      }
    }
    return ans;
  }
private
  boolean isPrime(int n) {
    for (int i = 2; i <= n / i; ++i) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int mostFrequentPrime(vector<vector<int>> &mat) {
    int m = mat.size(), n = mat[0].size();
    unordered_map<int, int> cnt;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int a = -1; a <= 1; ++a) {
          for (int b = -1; b <= 1; ++b) {
            if (a == 0 && b == 0) {
              continue;
            }
            int x = i + a, y = j + b, v = mat[i][j];
            while (x >= 0 && x < m && y >= 0 && y < n) {
              v = v * 10 + mat[x][y];
              if (isPrime(v)) {
                cnt[v]++;
              }
              x += a;
              y += b;
            }
          }
        }
      }
    }
    int ans = -1, mx = 0;
    for (auto &[v, x] : cnt) {
      if (mx < x || (mx == x && ans < v)) {
        mx = x;
        ans = v;
      }
    }
    return ans;
  }

private:
  bool isPrime(int n) {
    for (int i = 2; i <= n / i; ++i) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int: def is_prime(x: int) -> int: return all(x % i != 0 for i in range(2, isqrt(x) + 1)) m, n = len(mat), len(mat[0]) cnt = Counter() for i in range(m): for j in range(n): for a in range(- 1, 2): for b in range(- 1, 2): if a == 0 and b == 0: continue x, y, v = i + a, j + b, mat[i][j] while 0 <= x < m and 0 <= y < n: v = v * 10 + mat[x][y] if is_prime(v): cnt[v] += 1 x, y = x + a, y + b ans, mx = - 1, 0 for v, x in cnt . items(): if mx < x: mx = x ans = v elif mx == x: ans = max(ans, v) return ans

```