Most Frequent Prime
Source: leetcode
Difficulty: Medium
Tags: array, hash-table, math, matrix, counting, enumeration, number-theory

You are given a `m x n` **0\-indexed** 2Dmatrix `mat`. From every cell, you can create numbers in the following way:


- There could be at most `8` paths 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:**


**![](https://assets.leetcode.com/uploads/2024/02/15/south)** 

```


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.length`
- `n == mat[i].length`
- `1 <= m, n <= 6`
- `1 <= mat[i][j] <= 9`




C++ solution:
class Solution {
public:
    bool isPrime(int n) {
        if (n <= 1)
            return false;
        int sqrtN = sqrt(n);
        for (int i = 2; i <= sqrtN; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
    int mostFrequentPrime(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        int drow[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
        int dcol[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < 8; k++) {
                    int digit = mat[i][j];
                    int row = i + drow[k];
                    int col = j + dcol[k];
                    while (row >= 0 && row < n && col >= 0 && col < m) {
                        digit = digit * 10 + mat[row][col];
                        if (digit > 10) {
                            if (isPrime(digit))
                                mp[digit]++;
                        }
                        row += drow[k];
                        col += dcol[k];
                    }
                }
            }
        }
        if (mp.empty())
            return -1;
        int freq = 0;
        int ans;
        for (auto it : mp) {
            if (it.second >= freq) {
                if (freq == it.second)
                    ans = max(ans, it.first);
                else {
                    freq = it.second;
                    ans = it.first;
                }
            }
        }
        return ans;
    }
};

Go solution:
func mostFrequentPrime(mat [][]int) int {
	primeNumbersWithFrequency := map[int]int{}

	for i := 0; i < len(mat); i++ {
		for j := 0; j < len(mat[i]); j++ {
			makedNumbers := makeNumbersByTraveling8Paths(mat, i, j)
			for _, number := range makedNumbers {
				if _, ok := primeNumbersWithFrequency[number]; ok || IsPrimeNumber(number) {
					primeNumbersWithFrequency[number]++
				}
			}
		}
	}

    numberOfMostFrequency := 0
    mostFrequentPrime := -1

    for number, frequency := range primeNumbersWithFrequency {
        if number > 10 && frequency > numberOfMostFrequency{
            numberOfMostFrequency = frequency
            mostFrequentPrime = number
        }else if number > 10 && frequency == numberOfMostFrequency {
            if number > mostFrequentPrime {
                numberOfMostFrequency = frequency
                mostFrequentPrime = number
            }
        }
    }

	return mostFrequentPrime
}

func makeNumbersByTraveling8Paths(nums [][]int, CurrentColumnIndex, CurrentRowIndex int) []int {
	directions := [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {-1, 1}, {-1,-1}, {1, 1}, {1,-1}}
	numbers := []int{}

	for _, direction := range directions {
		directionForI := direction[0]
		directionForJ := direction[1]
		
		numberMakedTraveling := 0
		
		i := CurrentColumnIndex
		j := CurrentRowIndex
		for i >= 0 && i < len(nums) && j >= 0 && j < len(nums[CurrentColumnIndex]) {
			numberMakedTraveling = numberMakedTraveling * 10 + nums[i][j] 
			i += directionForI
			j += directionForJ
			numbers = append(numbers, numberMakedTraveling)
		}
	}

	return numbers
}

func IsPrimeNumber(number int) bool {
	if number == 1{
		return false
	}

	if number == 2 {
		return true
	}

	for i := 2; i <= number / 2; i++ {
		if number % i == 0 {
			return false
		}
	}
	return true
}

Java solution:
class Solution {
    public int mostFrequentPrime(int[][] mat) {
        List<Integer> res = new ArrayList<>();
        int n = mat.length, m = mat[0].length;
        int[] dx = {0, 0, 1, 1, 1, -1,-1, -1};
        int[] dy = {1, -1, 0, 1, -1, -1, 0, 1};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int dir = 0; dir < 8; dir++) {
                    dfs(res, 0, i, j, dx[dir], dy[dir], mat);
                }
            }
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : res) {
            if (num < 10 || !isPrime(num)) continue;
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        int maxCount = 0;
        int max = -1;
        for (int key : map.keySet()) {
            if (map.get(key) > maxCount) {
                maxCount = map.get(key);
                max = key;
            } else if (map.get(key) == maxCount) {
                max = Math.max(key, max);
            }
        }
        return max;
    }
    
    private void dfs(List<Integer> res, int pre, int i, int j, int dirX, int dirY, int[][] mat) {
        if (i < 0 || i >= mat.length || j < 0 || j >= mat[0].length) return;
        int num = pre * 10 + mat[i][j];
        res.add(num);
        dfs(res, num, i + dirX, j + dirY, dirX, dirY, mat);
    }
    
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

JavaScript solution:
/**
 * @param {number[][]} mat
 * @return {number}
 */
function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;

    if (n % 2 === 0 || n % 3 === 0) return false;

    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }

    return true;
}

var mostFrequentPrime = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, -1], [-1, 1]];
    const nums = new Map();

    let mostFrequentPrime = -1;
    let mostFrequentCount = 0;

    function dfs(i, j, path, direction) {
        if (i < 0 || i >= m || j < 0 || j >= n) return;

        path += mat[i][j];
        const num = parseInt(path);

        if (num > 10 && isPrime(num)) {
            const prev = nums.get(num) || 0;
            nums.set(num, prev + 1);
            const curr = prev + 1;

            if (curr > mostFrequentCount || curr === mostFrequentCount && num > mostFrequentPrime) {
                mostFrequentCount = curr;
                mostFrequentPrime = num;
            }
        }

        if (direction) {
            const [di, dj] = direction;
            dfs(i + di, j + dj, path, direction);
        } else {

            for(dir of directions) {
                const [di, dj] = dir;
                dfs(i + di, j + dj, path, dir);
            }
        }
    }

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            dfs(i, j, '');
        }
    }

    return mostFrequentPrime;
};

Python solution:
class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
        def isprime(num):
            fmax = int (math.ceil(pow(num, 0.5)))
            for i in range(2, fmax + 1):
                if num % i == 0:
                    return False
            return True
        
        
        dij = [[-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0]]
        cnt = defaultdict(int)
        m = len(mat)
        n = len(mat[0])
        for i in range(m):
            for j in range(n):
                for k in range(len(dij)):
                    num = mat[i][j]
                    inext, jnext = i + dij[k][0], j + dij[k][1]
                    while 0 <= inext < m and 0 <= jnext < n:
                        num = num * 10 + mat[inext][jnext]
                        cnt[num] += 1
                        inext += dij[k][0]
                        jnext += dij[k][1]

        ncnt = []
        for num in cnt:
            ncnt.append([cnt[num], num])

        ncnt.sort()
        for nc, num in reversed(ncnt):
            if isprime(num):
                return num
        return -1

Ruby solution:
# @param {Integer[][]} mat
# @return {Integer}
def most_frequent_prime(mat)
    m = mat.length
    n = mat[0].length
    res = Hash.new(0)
    
    for i in 0...m do
        for j in 0...n do
            dfs(mat, i, j, mat[i][j],res, nil)
        end
    end
    
    max_count = -1
    max = -1

    res.each do|k,v|
        if v > max_count
            max_count = v
            max = k
        elsif v == max_count && k > max
            max = k
        end
    end

    max
end

def dfs(mat, row, col, path, res, fixed_direction)
    m=mat.size
    n=mat[0].size
    res[path] += 1 if path > 10 && Prime.prime?(path)
    
    if fixed_direction == nil    
        dir = [[0,1], [1,1], [1,0], [1,-1],[0,-1], [-1,-1], [-1,0], [-1,1]]
        dir.each do|d|
            new_row = row + d[0]
            new_col = col + d[1]

            if new_row >= 0 && new_row < m && new_col >= 0 && new_col < n
                dfs(mat, new_row, new_col, path*10 + mat[new_row][new_col], res, d)
            end
        end
    else
        new_row = row + fixed_direction[0]
        new_col = col + fixed_direction[1]
        
        if new_row >= 0 && new_row < m && new_col >= 0 && new_col < n
            dfs(mat, new_row, new_col, path*10 + mat[new_row][new_col], res, fixed_direction)
        end
    end
end