3044. Most Frequent Prime LeetCode Solution

In this guide, you will get 3044. Most Frequent Prime LeetCode Solution with the best time and space complexity. The solution to Most Frequent Prime problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Most Frequent Prime solution in C++
  4. Most Frequent Prime solution in Java
  5. Most Frequent Prime solution in Python
  6. Additional Resources
3044. Most Frequent Prime LeetCode Solution image

Problem Statement of Most Frequent Prime

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 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:

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:

See also  473. Matchsticks to Square LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(mn \cdot \max(m, n))
  • Space Complexity: O(1)

3044. Most Frequent Prime LeetCode Solution in C++

class Solution {
 public:
  int mostFrequentPrime(vector<vector<int>>& mat) {
    constexpr int dirs[8][2] = {{1, 0},  {1, -1}, {0, -1}, {-1, -1},
                                {-1, 0}, {-1, 1}, {0, 1},  {1, 1}};
    const int m = mat.size();
    const int n = mat[0].size();
    int ans = -1;
    int maxFreq = 0;
    unordered_map<int, int> count;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (const auto& [dx, dy] : dirs) {
          int num = 0;
          for (int x = i, y = j; 0 <= x && x < m && 0 <= y && y < n;
               x += dx, y += dy) {
            num = num * 10 + mat[x][y];
            if (num > 10 && isPrime(num))
              ++count[num];
          }
        }

    for (const auto& [prime, freq] : count)
      if (freq > maxFreq) {
        ans = prime;
        maxFreq = freq;
      } else if (freq == maxFreq) {
        ans = max(ans, prime);
      }

    return ans;
  }

 private:
  bool isPrime(int num) {
    for (int i = 2; i < sqrt(num) + 1; ++i)
      if (num % i == 0)
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

3044. Most Frequent Prime LeetCode Solution in Java

class Solution {
  public int mostFrequentPrime(int[][] mat) {
    final int[][] dirs = {{1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}};
    final int m = mat.length;
    final int n = mat[0].length;
    int ans = -1;
    int maxFreq = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int[] dir : dirs) {
          int num = 0;
          int x = i;
          int y = j;
          while (0 <= x && x < m && 0 <= y && y < n) {
            num = num * 10 + mat[x][y];
            if (num > 10 && isPrime(num))
              count.merge(num, 1, Integer::sum);
            x += dir[0];
            y += dir[1];
          }
        }

    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
      final int prime = entry.getKey();
      final int freq = entry.getValue();
      if (freq > maxFreq) {
        ans = prime;
        maxFreq = freq;
      } else if (freq == maxFreq) {
        ans = Math.max(ans, prime);
      }
    }

    return ans;
  }

  private boolean isPrime(int num) {
    for (int i = 2; i < (int) Math.sqrt(num) + 1; ++i)
      if (num % i == 0)
        return false;
    return true;
  }
}
// code provided by PROGIEZ

3044. Most Frequent Prime LeetCode Solution in Python

class Solution:
  def mostFrequentPrime(self, mat: list[list[int]]) -> int:
    dirs = ((1, 0), (1, -1), (0, -1), (-1, -1),
            (-1, 0), (-1, 1), (0, 1), (1, 1))
    m = len(mat)
    n = len(mat[0])
    count = collections.Counter()

    def isPrime(num: int) -> bool:
      return not any(num % i == 0 for i in range(2, int(num**0.5 + 1)))

    for i in range(m):
      for j in range(n):
        for dx, dy in dirs:
          num = 0
          x = i
          y = j
          while 0 <= x < m and 0 <= y < n:
            num = num * 10 + mat[x][y]
            if num > 10 and isPrime(num):
              count[num] += 1
            x += dx
            y += dy

    if not count.items():
      return -1
    return max(count.items(), key=lambda x: (x[1], x[0]))[0]
# code by PROGIEZ

Additional Resources

See also  2549. Count Distinct Numbers on Board LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.