3044. Most Frequent Prime
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.
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
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.
Depth first search can be used to find whether two components in a graph are connected.
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.
2is a prime number but is not greater than10.23is a prime number and is greater than10, so it gets counted.235is 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
491class 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}
661#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};
631function 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}
61A heap is a ...?
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
mrows andncolumns of the matrixmat, which gives us a starting complexity ofO(m * n). - Inside the nested loops, for each cell there are 8 possible directions to move (since
aandbcan each be -1, 0, or 1, except when they are both 0). Hence, we can consider the combination of these two nested loops asO(8 * m * n), which simplifies toO(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 getO(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, takeO(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
Counterfrom Python'scollectionsmodule 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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching 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.