#3044

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Most Frequent Prime

Find the most frequent prime over 10 from numbers generated by scanning a 2D matrix in all straight directions efficiently.

array hash table math matrix counting

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 m n and the maximum number length generated from each cell, roughly O(m n*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.

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.

terminal

Solution

Solution 1: Hash Table + Enumeration

We can use a hash table to count the frequency of each prime number greater than 10.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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 ans

Continue Practicing

#3312 sorted gcd pair queries #2748 number of beautiful pairs #3591 check if any element has prime frequency