We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Most Frequent Prime

Difficulty: Medium

Problem Description

You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers by traversing in one of the 8 possible directions. You need to return the most frequent prime number greater than 10 from all the numbers formed, or -1 if no such prime exists. If there are multiple prime numbers with the highest frequency, return the largest among them.

Key Insights

  • You can generate numbers by traversing in 8 possible directions from each cell.
  • Numbers are created progressively as you append digits during traversal.
  • Only prime numbers greater than 10 are of interest.
  • Efficient prime checking and counting are necessary due to potentially large numbers formed.
  • The algorithm must handle cells in a matrix with dimensions up to 6x6.

Space and Time Complexity

Time Complexity: O(m * n * k), where k is the maximum length of numbers generated from any cell. Space Complexity: O(p), where p is the number of unique prime numbers found in the results.

Solution

The solution involves the following steps:

  1. Define the possible directions for traversal.
  2. For each cell in the matrix, generate numbers by traversing in each of the 8 directions.
  3. Use a hashmap to count the frequency of each prime number greater than 10.
  4. Check if a number is prime using a helper function.
  5. After processing all cells, determine the most frequent prime number, considering ties by selecting the largest prime.

Code Solutions

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def most_frequent_prime(mat):
    from collections import defaultdict
    
    directions = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]
    prime_count = defaultdict(int)
    
    m, n = len(mat), len(mat[0])
    
    for i in range(m):
        for j in range(n):
            for dx, dy in directions:
                num_str = ""
                x, y = i, j
                
                while 0 <= x < m and 0 <= y < n:
                    num_str += str(mat[x][y])
                    num = int(num_str)
                    if num > 10 and is_prime(num):
                        prime_count[num] += 1
                    x += dx
                    y += dy
    
    most_frequent = -1
    max_frequency = 0
    
    for prime, count in prime_count.items():
        if count > max_frequency or (count == max_frequency and prime > most_frequent):
            most_frequent = prime
            max_frequency = count
    
    return most_frequent
← Back to All Questions