You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers in the following way:
8 paths from the cells namely: east, south-east, south, south-west, west, north-west, north, and north-east.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:
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.lengthn == mat[i].length1 <= m, n <= 61 <= mat[i][j] <= 9In #3044 Most Frequent Prime, the goal is to form numbers by traversing a digit matrix in all 8 possible directions. Starting from every cell, repeatedly move in the same direction and build numbers by appending digits. For each generated value, check whether it is a prime number greater than 10 and track its frequency using a hash table.
The key idea is directional enumeration. For each cell, explore all eight directions and keep extending the number until the boundary of the grid is reached. Each time a new number is formed, perform a prime check and record its occurrence. A hash map stores the frequency of each prime encountered.
To optimize prime checks, either use a sqrt(n) primality test or precompute primes using a sieve up to the maximum possible value formed from the grid digits. After processing all paths, select the prime with the highest frequency, breaking ties by choosing the largest prime.
This approach leverages enumeration, hashing, and number theory to efficiently analyze all valid digit sequences.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Directional Enumeration with Hash Map | O(m * n * 8 * L) | O(P) |
| With Sieve for Prime Checks | O(V log log V + m * n * 8 * L) | O(V) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use recursion to find all possible numbers for each cell and then check for prime.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like Most Frequent Prime reflect common FAANG interview patterns involving grid traversal, enumeration, hashing, and number theory. While the exact problem may vary, similar matrix enumeration and prime-checking tasks frequently appear in technical interviews.
The optimal strategy is to enumerate numbers from every matrix cell in all eight directions while building numbers digit by digit. Each generated number is checked for primality and counted using a hash map. Finally, the prime with the highest frequency (and largest value in case of ties) is returned.
You can check primes using a square-root primality test for each number or precompute primes using a sieve up to the maximum possible value formed from the grid. The sieve approach is faster when many numbers need to be tested.
A hash map (or dictionary) is ideal for storing the frequency of each prime number encountered. It allows constant-time updates and makes it easy to determine the most frequent prime after processing all matrix paths.