This problem requires generating all numbers from each matrix cell along valid directions and counting primes over 10. Using recursion to explore each path and a hash map to track frequency ensures we can quickly identify the most frequent prime. If no prime above 10 exists, return -1; if there is a tie, return the largest prime.
Problem Statement
Given an m x n 0-indexed 2D matrix, generate numbers from every cell by moving in straight directions without changing direction. Each move appends the digit from the cell to form multi-digit numbers.
Return the most frequent prime number greater than 10 among all generated numbers. If multiple primes share the highest frequency, return the largest. If no prime exists, return -1.
Examples
Example 1
Input: mat = [[1,1],[9,9],[1,1]]
Output: 19
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
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
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 Approach
Recursive number generation
From each matrix cell, recursively move in all four straight directions, building numbers by concatenating digits. Stop recursion when bounds are exceeded.
Frequency counting with hash map
Maintain a hash map to count occurrences of each number greater than 10. Only consider numbers that are prime during the counting process.
Select the most frequent prime
Iterate over the hash map to find the prime with the highest frequency. If multiple primes tie, select the largest one. Return -1 if no valid prime exists.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on the number of cells mn and the maximum number length generated from each cell, roughly O(mn*maxLen). Space complexity is dominated by the hash map storing generated numbers, O(uniqueNumbers).
What Interviewers Usually Probe
- Checks if you can efficiently explore all paths from each cell using recursion.
- Observes if you can apply a hash map to track number frequencies correctly.
- Tests your ability to combine number theory with array scanning patterns.
Common Pitfalls or Variants
Common pitfalls
- Failing to stop recursion when moving out of matrix bounds.
- Counting non-prime numbers or primes less than or equal to 10.
- Incorrectly choosing between tied primes without selecting the largest.
Follow-up variants
- Return the smallest most frequent prime instead of the largest when ties occur.
- Allow numbers formed by moving in any direction, including diagonals, changing directions mid-path.
- Count frequencies for all numbers, not just primes, to find the most common number in the matrix.
How GhostInterview Helps
- Automatically generates all numbers from each cell and applies the prime check without manual enumeration.
- Highlights frequency counting mistakes and ensures the largest prime is returned when there is a tie.
- Optimizes recursion and hash map usage to avoid redundant computations and reduce time complexity.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient approach for the Most Frequent Prime problem?
Use recursion to explore numbers from each cell and a hash map to track frequencies of primes over 10, then select the most frequent.
How do I handle ties in the Most Frequent Prime problem?
Compare all primes with the highest frequency and return the largest prime among them.
Can numbers smaller than 10 be considered primes here?
No, only primes strictly greater than 10 are considered valid for this problem.
Does changing direction in the matrix affect the result?
Yes, changing direction is invalid. Numbers must be formed by moving straight in one direction from the starting cell.
Is hash map usage necessary for Most Frequent Prime?
While not strictly required, a hash map efficiently tracks the frequency of generated numbers and identifies the most frequent prime.
Need direct help with Most Frequent Prime instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Most Frequent Prime from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve the Sorted GCD Pair Queries problem by efficiently counting and locating GCDs of all array pairs using hash mapping.
Open problem page#2748 Number of Beautiful PairsCount all index pairs in an array where the first digit of one number and last digit of another are coprime efficiently.
Open problem page#3591 Check if Any Element Has Prime FrequencyCheck if any element in the array has a prime frequency count, leveraging array scanning and hash table lookup.
Open problem page