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] <= 9Problem Overview: You are given a matrix of digits. Starting from any cell, build numbers by moving through the grid and concatenating digits along the path. Every number formed is checked for primality, and the task is to return the prime that appears most frequently. If multiple primes have the same frequency, return the largest one.
Approach 1: Depth First Search (DFS) with Path Tracking (O(m * n * k), Space: O(P))
This approach treats the grid like a search space and explores number formations using DFS. From each cell, move in all eight possible directions and keep appending digits to build numbers step by step. Each time a new number is formed, run a primality test and update its frequency in a hash map. The key insight is incremental number construction: instead of recomputing digits each time, multiply the current value by 10 and append the next digit. DFS naturally handles path exploration and ensures all directional sequences are checked. Time complexity is O(m * n * k) where k is the maximum path length, and space complexity is O(P) for storing counts of discovered primes.
This method works well because matrix traversal and incremental number building are efficient. A hash map from the Hash Table category keeps track of prime frequencies. Primality checking relies on basic Number Theory techniques such as checking divisibility up to the square root.
Approach 2: Backtracking Focused on Matrix Paths (O(m * n * k), Space: O(P + k))
Backtracking explores digit sequences similarly but focuses explicitly on matrix paths. Start from each cell and recursively extend the current number while moving in a fixed direction. Each recursive step appends a digit, evaluates whether the new value is prime, and records it in a frequency map. Because the path continues until it exits the grid boundary, recursion depth stays bounded by the grid dimension. Backtracking makes the state transition clear: current position, current number, and chosen direction.
This approach is easier to reason about when modeling the grid as a path-building problem from the Matrix traversal family. The algorithm maintains a global counter for primes and updates the most frequent candidate during traversal. Time complexity remains O(m * n * k) and space complexity is O(P + k), where k represents recursion depth.
Recommended for interviews: The DFS enumeration approach is typically expected. Interviewers want to see that you recognize the grid traversal pattern, generate numbers incrementally, and store frequencies using a hash map. Demonstrating brute enumeration of paths shows problem understanding, but combining traversal with efficient prime checking and counting shows stronger algorithmic skill.
This approach uses Depth First Search to explore all paths from each cell in the matrix. For each path, we generate numbers by appending digits step-by-step. Then, we check if these numbers are prime and track their frequencies. Finally, we determine the most frequent prime number greater than 10.
The solution uses a recursive DFS function to explore paths from each cell. Each new digit forms and extends numbers by traversing in specified directions, and these paths are checked for prime conditions (>10). The function counts these primes and determines the one with the highest frequency.
Time Complexity: O(8^(m * n)) - Due to exponential path exploration in recursion.
Space Complexity: O(m * n) for recursion stack and prime tracking.
This approach introduces backtracking to optimize search in the matrix for prime number paths. For every starting cell, the method attempts all potential valid paths holding a number construct as it explores, abandoning paths prematurely when they're deemed non-promising.
The C++ implementation enhances path exploration by using a backtracking strategy to navigate potential paths of digits forming numbers, checking for primes only when paths gather enough digits. This incremental path decision prevents excessive memory use and focuses computational effort on promising paths.
C++
JavaScript
Time Complexity: O(8^(m * n)) - Due to potential path exploration.
Space Complexity: O(m * n) for embedding matrix and track past visited configurations.
We can use a hash table to count the frequency of each prime number greater than 10.
For each cell, we can start from it, generate a number along one of the 8 directions, and then determine whether the generated number is a prime number greater than 10. If it is, we add it to the hash table.
Finally, we traverse the hash table to find the prime number with the highest frequency. If there are multiple prime numbers with the highest frequency, we return the largest one.
The time complexity is O(m times n times max(m, n) times {10}^{\frac{max(m, n)}{2}}), and the space complexity is O(m times n times max(m, n)). Here, m and n are the number of rows and columns of mat, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Path Tracking | Time Complexity: O(8^(m * n)) - Due to exponential path exploration in recursion. Space Complexity: O(m * n) for recursion stack and prime tracking. |
| Backtracking Focused on Matrix Paths | Time Complexity: O(8^(m * n)) - Due to potential path exploration. Space Complexity: O(m * n) for embedding matrix and track past visited configurations. |
| Hash Table + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Path Tracking | O(m * n * k) | O(P) | General case when enumerating all directional number formations in the grid |
| Backtracking on Matrix Paths | O(m * n * k) | O(P + k) | Useful when modeling the problem explicitly as recursive path exploration |
Most Frequent Prime | Leetcode 3044 • Ayushi Sharma • 782 views views
Watch 6 more video solutions →Practice Most Frequent Prime with our built-in code editor and test cases.
Practice on FleetCode