Skip to content

3044. Most Frequent Prime

  • Time: $O(mn \cdot \max(m, n))$
  • Space: $O(1)$
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  int mostFrequentPrime(vector<vector<int>>& mat) {
    constexpr int kDirs[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] : kDirs) {
          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;
  }
};

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
  }
}

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