Watch 7 video solutions for Most Frequent Prime, a medium level problem involving Array, Hash Table, Math. This walkthrough by Ayushi Sharma has 782 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |