Most Frequent Prime
MedPrompt
You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers in the following way:
- There could be at most
8paths 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:
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] <= 9
Approaches
2 approaches with complexity analysis and trade-offs.
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.
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
dfrom 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 > 10andisPrime(currentNum):freqMap.put(currentNum, freqMap.getOrDefault(currentNum, 0) + 1).
- Update
currR += dr[d],currC += dc[d].
- Initialize
- For each direction
- Find the most frequent prime from
freqMap. - Return the result or -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Determine
MAX_VAL(e.g.,1,000,000). - Create a boolean array
isNotPrimeof sizeMAX_VAL. - Run Sieve of Eratosthenes on
isNotPrimeto 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 > 10and!isNotPrime[currentNum]:- Update
freqMap.
- Update
- Traverse the path, building
- For each of the 8 directions
- Find the most frequent prime from
freqMap. - Return the result or -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.