3044. Most Frequent Prime

MediumArrayHash TableMathCountingEnumerationMatrixNumber Theory
Leetcode Link

Problem Description

In this problem, we are given a 2D matrix with integers, and from each cell of this matrix, we are tasked with creating a series of numbers. We can generate these numbers by choosing one of eight possible paths (east, south-east, south, south-west, west, north-west, north, and north-east) and moving cell by cell in the chosen direction. As we move along a path, we append the digit from each cell to form a new number, obtaining a series of numbers from the concatenation of these digits. Importantly, each intermediate number is also considered a generated number. Our goal is to find the prime number greater than 10 that appears most frequently among all numbers created this way. If there are multiple such prime numbers, we should return the largest one. If no prime numbers greater than 10 are generated, the result should be -1.

To illustrate, consider a matrix path that has the digits 4, 5, and 7 when traveling to the east. The generated numbers on this path would be 4, 45, and 457. If 457 is a prime number (and greater than 10), it would be counted for our final result.

This problem involves understanding both prime number determination and how to efficiently search through all possible paths in a matrix to generate and count numbers.

Intuition

Behind the solution is the idea of brute force with optimization. We traverse each cell of the matrix and from each cell, move along each of the eight possible directions to generate numbers. Since movement is allowed only in straight lines along the given paths and there is no need for checking combinations of different paths, the process is straightforward but exhaustive.

As we generate numbers, we determine if they are prime and greater than 10. Rather than checking every number from scratch, we build on the previous number by multiplying it by 10 and adding the new digit, which is an efficient way to generate the sequence of numbers while traveling along a path.

To determine if a number is prime, we use a helper function that checks divisibility of the number by all integers up to the square root of that number. The prime checking is the most computationally intensive part of this solution, so efficiency here is crucial.

Once we have determined which numbers are prime, we use a Counter (a hash table) to keep track of how many times each prime number appears. After generating and counting all the prime numbers, we examine the Counter to find the prime number with the highest frequency.

However, we must consider two additional conditions: if multiple primes occur with the same highest frequency, we must return the largest prime; and if no prime numbers greater than 10 are found, we return -1.

This solution approach thus combines generation of all possible numbers along straight paths in the matrix, prime number identification, and the use of a Counter to efficiently find the most frequent prime that satisfies the problem's conditions.

Learn more about Math patterns.

Solution Approach

The solution uses a brute-force approach to traverse each cell of the matrix and to explore all the possible numbers that can be generated along the eight directions. The key aspects of the implementation include prime number checking, counting frequencies, and choosing the most frequent (and largest if necessary) prime number.

Prime Number Checking

To check whether a number is prime, the implementation uses a helper function is_prime(x). This function works on the principle that a number x is prime if it has no divisors other than 1 and itself. Therefore, it checks for no divisibility by any number from 2 up to the square root of x, denoted by isqrt(x) + 1. The operation isqrt(x) efficiently calculates the integer square root of x. The function all() is applied to the comprehension [x % i != 0 for i in range(2, isqrt(x) + 1)], ensuring that x is only considered prime if it is not divisible by any of the numbers in the range.

Counting Frequencies

The Counter from the collections library is used to keep a tally of the frequency of prime numbers encountered. This data structure is essentially a hash table specialized for counting occurrences. As each prime number is generated, its count is incremented by one in the Counter.

Generating Numbers

To generate the numbers, the algorithm uses four nested loops: the outermost two loop over all cells in the matrix, and the inner two loop over the eight directions. Directional movement is determined by pairs of integers (a, b) which represent the directional step from the current (x, y) cell. The condition if a == 0 and b == 0 is used to skip the case where there's no directional movement (which isn't a valid path).

Starting from the initial cell (i, j), the number v is initialized with the value from that cell. Then, as long as the next cell (x, y) is within the bounds of the matrix (0 <= x < m and 0 <= y < n), the new digit from mat[x][y] is appended to v by the operation v = v * 10 + mat[x][y]. After each digit is added, the number v is checked for primality, and if it is a prime greater than 10, it is counted in the Counter.

Selecting the Result

After all numbers are generated and counted, the algorithm iterates over the items in the Counter. A pair of variables, ans (to store the answer) and mx (to store the maximum frequency), are used to keep track of the most frequent prime number. When a number v with a frequency x is encountered, the algorithm updates ans and mx accordingly if x is greater than mx or if x equals mx and v is greater than ans.

This guarantees that, in the end, ans holds the largest prime number with the highest frequency above 10, or -1 if no suitable prime numbers are found.

By carefully choosing how to traverse the matrix and count prime numbers, the solution systematically handles the problem requirements and finds the correct result in an efficient manner.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's consider a small 3x3 matrix to illustrate the solution approach:

12 3 5
27 8 1
34 9 0

Step 1: Choose a starting cell

We start at the top-left cell with the value 2.

Step 2: Explore all eight directions

From here, let's move east (right), giving us the path 2 -> 3 -> 5.

Step 3: Generate numbers & check for primes

As we move, we generate numbers: 2, 23, and 235.

  • 2 is a prime number but is not greater than 10.
  • 23 is a prime number and is greater than 10, so it gets counted.
  • 235 is not a prime number.

Step 4: Repeat the process for all other cells

We then continue this process starting from all other cells (such as 3, 5, 7, etc.) and consider all eight directions every time.

Step 5: Counting frequencies

Suppose after traversing the whole matrix, we find that the prime number 23 appeared twice, prime 71 appeared three times, and prime 17 also appeared twice.

Step 6: Select the most frequent prime

Based on our counts, the most frequent prime number is 71 which appeared three times. Even though 23 and 17 both appeared twice, 71 is the most frequent.

Step 7: Address tie conditions or no primes

There are no tie conditions in this case, and since we found prime numbers greater than 10, we do not return -1.

Result

The final result for this 3x3 matrix is the prime number 71.

Solution Implementation

1from math import isqrt
2from collections import Counter
3
4class Solution:
5    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
6        # Helper function to check if a number is prime
7        def is_prime(num: int) -> bool:
8            if num < 2:
9                return False
10            return all(num % i != 0 for i in range(2, isqrt(num) + 1))
11
12        # Dimensions of the matrix
13        rows, cols = len(mat), len(mat[0])
14        # Counter to keep track of prime number frequencies
15        prime_count = Counter()
16      
17        # Iterate through all elements in the matrix
18        for i in range(rows):
19            for j in range(cols):
20                # Explore all eight directions from each cell
21                for a in range(-1, 2):
22                    for b in range(-1, 2):
23                        # Skip the direction that points to the current cell itself
24                        if a == 0 and b == 0:
25                            continue
26                        x, y = i, j
27                        sequence = mat[i][j]
28                        # Continue moving in the direction (a, b) as long as we're within bounds
29                        while 0 <= x < rows and 0 <= y < cols:
30                            sequence = sequence * 10 + mat[x][y]
31                            if is_prime(sequence):
32                                prime_count[sequence] += 1
33                            x += a
34                            y += b
35      
36        # Find the most frequent prime number
37        most_frequent_prime, max_frequency = -1, 0
38        for prime, frequency in prime_count.items():
39            # If the current frequency is greater than max_frequency, update the results
40            if frequency > max_frequency:
41                max_frequency = frequency
42                most_frequent_prime = prime
43            # If there is a tie, take the larger prime number
44            elif frequency == max_frequency:
45                most_frequent_prime = max(most_frequent_prime, prime)
46      
47        # Return the most frequently occurring prime number
48        return most_frequent_prime
49
1class Solution {
2
3    // Method to find the most frequent prime number
4    public int mostFrequentPrime(int[][] mat) {
5        int rows = mat.length, cols = mat[0].length; // Obtain matrix dimensions
6        Map<Integer, Integer> primeFrequency = new HashMap<>(); // Map to store counts of prime numbers
7
8        // Iterate over the matrix
9        for (int i = 0; i < rows; ++i) {
10            for (int j = 0; j < cols; ++j) {
11                // Check in all directions around a cell
12                for (int deltaX = -1; deltaX <= 1; ++deltaX) {
13                    for (int deltaY = -1; deltaY <= 1; ++deltaY) {
14                        // Skip checking the same cell
15                        if (deltaX == 0 && deltaY == 0) {
16                            continue;
17                        }
18                        int x = i + deltaX, y = j + deltaY;
19                        int number = mat[i][j]; // Start with the current cell value
20
21                        // Move in the direction delta increments until out of bounds
22                        while (x >= 0 && x < rows && y >= 0 && y < cols) {
23                            // Append the digit from the current cell to the number
24                            number = number * 10 + mat[x][y];
25                            // If it's a prime, increase its count in the map
26                            if (isPrime(number)) {
27                                primeFrequency.merge(number, 1, Integer::sum);
28                            }
29                            x += deltaX; // Move in the deltaX direction
30                            y += deltaY; // Move in the deltaY direction
31                        }
32                    }
33                }
34            }
35        }
36
37        // Find the prime with the highest frequency
38        int mostFrequent = -1, maxFrequency = 0;
39        for (Map.Entry<Integer, Integer> entry : primeFrequency.entrySet()) {
40            int prime = entry.getKey();
41            int frequency = entry.getValue();
42            // Check if the current frequency is greater than maxFrequency
43            // Or if the current frequency is the same and prime is a larger number
44            if (frequency > maxFrequency || (frequency == maxFrequency && mostFrequent < prime)) {
45                maxFrequency = frequency;
46                mostFrequent = prime;
47            }
48        }
49        // Return the most frequent prime number
50        return mostFrequent;
51    }
52
53    // Helper method to check if a number is prime
54    private boolean isPrime(int n) {
55        if (n <= 1) return false; // Numbers less than 2 are not prime numbers
56        for (int i = 2; i <= n / i; ++i) {
57            // If n is divisible by i, it's not a prime number
58            if (n % i == 0) {
59                return false;
60            }
61        }
62        // If no divisor is found, n is a prime number
63        return n > 1;
64    }
65}
66
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the most frequent prime number formed by concatenating 
8    // numbers in all eight directions from every entry in the matrix.
9    int mostFrequentPrime(vector<vector<int>>& mat) {
10        int rows = mat.size(), cols = mat[0].size();
11        unordered_map<int, int> primeFrequency;
12
13        // Traverse the matrix.
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                // Check all eight directions from the current cell.
17                for (int rowDelta = -1; rowDelta <= 1; ++rowDelta) {
18                    for (int colDelta = -1; colDelta <= 1; ++colDelta) {
19                        // Skip the case where both deltas are zero as there's no direction defined.
20                        if (rowDelta == 0 && colDelta == 0) {
21                            continue;
22                        }
23                        int x = i + rowDelta, y = j + colDelta;
24                        int value = mat[i][j];
25                        // Move in the specified direction and form numbers by concatenation.
26                        while (x >= 0 && x < rows && y >= 0 && y < cols) {
27                            value = value * 10 + mat[x][y];
28                            // If the formed number is prime, update its frequency.
29                            if (isPrime(value)) {
30                                primeFrequency[value]++;
31                            }
32                            x += rowDelta;
33                            y += colDelta;
34                        }
35                    }
36                }
37            }
38        }
39
40        int mostFrequent = -1, maxFrequency = 0;
41        // Find the prime number with maximum frequency.
42        for (auto& [prime, frequency] : primeFrequency) {
43            if (maxFrequency < frequency || (maxFrequency == frequency && mostFrequent < prime)) {
44                maxFrequency = frequency;
45                mostFrequent = prime;
46            }
47        }
48        return mostFrequent;
49    }
50
51private:
52    // Helper function to determine if a number is a prime.
53    bool isPrime(int num) {
54        if (num <= 1) return false; // 0 and 1 are not prime numbers.
55        for (int i = 2; i <= num / i; ++i) {
56            if (num % i == 0) {
57                return false;
58            }
59        }
60        return true;
61    }
62};
63
1function mostFrequentPrime(mat: number[][]): number {
2    // Extract matrix dimensions
3    const rows: number = mat.length;
4    const cols: number = mat[0].length;
5
6    // Initialize a map to store the frequency of prime numbers
7    const count: Map<number, number> = new Map();
8
9    // Helper function to check if a number is prime
10    const isPrime = (num: number): boolean => {
11        for (let i = 2; i <= num / i; ++i) {
12            if (num % i === 0) {
13                return false;
14            }
15        }
16        return num > 1;
17    };
18
19    // Iterate through each element in the matrix
20    for (let i = 0; i < rows; ++i) {
21        for (let j = 0; j < cols; ++j) {
22            // Check in all 8 directions from the current element
23            for (let deltaX = -1; deltaX <= 1; ++deltaX) {
24                for (let deltaY = -1; deltaY <= 1; ++deltaY) {
25                    // Skip if the direction is pointing to the original element
26                    if (deltaX === 0 && deltaY === 0) {
27                        continue;
28                    }
29                    // Start building a number from the current element in the current direction
30                    let [currentX, currentY, value] = [i + deltaX, j + deltaY, mat[i][j]];
31                    // Keep appending digits in the current direction until out of bounds
32                    while (currentX >= 0 && currentX < rows && currentY >= 0 && currentY < cols) {
33                        value = value * 10 + mat[currentX][currentY];
34                        // Check if the newly formed number is prime and update the frequency map
35                        if (isPrime(value)) {
36                            count.set(value, (count.get(value) || 0) + 1);
37                        }
38                        currentX += deltaX;
39                        currentY += deltaY;
40                    }
41                }
42            }
43        }
44    }
45
46    // Initialize variables to find the most frequent and largest prime number
47    let [answer, maxFrequency] = [-1, 0];
48
49    // Iterate through the count map to find the answer
50    count.forEach((frequency, primeNumber) => {
51        // Update the answer if the current frequency is greater than the maxFrequency found so far
52        // or if the frequencies are equal but the current prime number is greater
53        if (maxFrequency < frequency || (maxFrequency === frequency && answer < primeNumber)) {
54            maxFrequency = frequency;
55            answer = primeNumber;
56        }
57    });
58
59    return answer;
60}
61

Time and Space Complexity

The time complexity of the given code can be analyzed as follows:

  • There are two nested loops that iterate through the m rows and n columns of the matrix mat, which gives us a starting complexity of O(m * n).
  • Inside the nested loops, for each cell there are 8 possible directions to move (since a and b can each be -1, 0, or 1, except when they are both 0). Hence, we can consider the combination of these two nested loops as O(8 * m * n), which simplifies to O(m * n) since constants are ignored in Big O notation.
  • For each direction, there's a while loop which in worst case travels the maximum length across the matrix, which is max(m, n). Thus, including this factor, we get O(m * n * max(m, n)).
  • In the worst case, the number while loop could be iterating is a number with as many digits as max(m, n) because we append a digit in each iteration. Therefore, checking whether such a large number is prime or not can, in the worst case, take O(10^(max(m, n) / 2)) because checking for prime numbers involves testing divisibility up to the square root of the number.

Combining these factors, the total time complexity is O(m * n * max(m, n) * 10^(max(m, n) / 2)).

For the space complexity:

  • We are using a Counter from Python's collections module to store the frequency of occurrences of each prime number. The worst-case space complexity would be if every possible number the loop generates is unique and prime.
  • This theoretically gives us O(m * n * max(m, n)) for the space complexity, as the maximum number of unique primes we could store would be proportional to the number of different positions and directions we are generating these numbers from, considering every generated number is prime.

In summary, the time complexity is O(m * n * max(m, n) * 10^(max(m, n) / 2)) and space complexity is O(m * n * max(m, n)).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄