Problem Description

You are given a m x n matrix mat containing single digits (0-9). Your task is to find numbers by traversing the matrix in straight lines and determine which prime number appears most frequently.

From each cell in the matrix, you can move in 8 possible directions:

• East (right)
• South-east (diagonal down-right)
• South (down)
• South-west (diagonal down-left)
• West (left)
• North-west (diagonal up-left)
• North (up)
• North-east (diagonal up-right)

When traversing in any direction, you form numbers by concatenating the digits you encounter. For example, if you traverse cells containing digits 1, 9, 1 in sequence, you create three numbers: 1, 19, and 191.

Rules and requirements:

• You must move in a straight line (cannot change direction during a single traversal)
• Only count prime numbers that are greater than 10
• Count how many times each valid prime number appears across all possible traversals from all starting positions
• Return the prime number that appears most frequently
• If multiple prime numbers have the same highest frequency, return the largest one among them
• If no prime number greater than 10 exists, return -1

For example, starting from a cell with digit 1, if you move east and encounter 9, you've created the number 19. If 19 is prime and greater than 10, it gets counted. If you continue east and encounter 1, you've now created 191, which also gets evaluated and counted if it's prime.

Intuition

The key insight is that we need to systematically explore all possible number formations from every cell in the matrix. Since we can move in 8 directions and must continue in a straight line, this naturally suggests a traversal approach.

Think of each cell as a potential starting point. From any cell (i, j), we can imagine drawing straight lines in all 8 directions. As we move along each line, we're essentially building numbers digit by digit - like typing digits on a calculator where each new digit shifts the previous number left by one decimal place (multiply by 10) and adds the new digit.

The mathematical pattern for building numbers is straightforward: if we have a number v and encounter a new digit d, the new number becomes v * 10 + d. For instance, if we have 19 and encounter 1, we get 19 * 10 + 1 = 191.

For the direction movement, we can use direction vectors. Each direction can be represented by a pair (a, b) where a is the row change (-1, 0, or 1) and b is the column change (-1, 0, or 1). This gives us 9 combinations, but we exclude (0, 0) since that means no movement.

To track frequencies, a hash table (Counter) is perfect - it naturally handles counting occurrences of each prime number we find. As we generate each number along a path, we check if it's prime and greater than 10, then increment its count.

The prime checking itself is a standard algorithm - we only need to check divisibility up to the square root of the number, making it efficient enough for this problem.

Finally, finding the most frequent prime is a simple scan through our frequency table, keeping track of the maximum frequency and updating our answer when we find a higher frequency or a larger prime with the same frequency.

Learn more about Math patterns.

Solution Approach

The solution uses a hash table combined with exhaustive enumeration to solve this problem efficiently.

Step 1: Initialize Data Structures

• Use a Counter (hash table) to track the frequency of each prime number encountered
• Get matrix dimensions m and n for boundary checking

Step 2: Enumerate All Starting Positions Iterate through each cell (i, j) in the matrix as a potential starting point:

for i in range(m):
    for j in range(n):

Step 3: Explore All 8 Directions For each starting cell, try all 8 directions using direction vectors (a, b):

for a in range(-1, 2):
    for b in range(-1, 2):
        if a == 0 and b == 0:
            continue  # Skip no movement

The pairs (a, b) represent:

• (-1, -1): North-west
• (-1, 0): North
• (-1, 1): North-east
• (0, -1): West
• (0, 1): East
• (1, -1): South-west
• (1, 0): South
• (1, 1): South-east

Step 4: Traverse and Build Numbers Starting from position (i, j), move in direction (a, b):

• Initialize with the starting cell's digit: v = mat[i][j]
• Move to the next cell: x, y = i + a, j + b
• Continue while within bounds: 0 <= x < m and 0 <= y < n
• Build the number: v = v * 10 + mat[x][y]
• Check if it's a prime greater than 10 and update the counter
• Move to the next cell in the same direction: x, y = x + a, y + b

Step 5: Prime Checking The helper function is_prime(x) checks if a number is prime by testing divisibility from 2 to sqrt(x):

all(x % i != 0 for i in range(2, isqrt(x) + 1))

This is efficient since any composite number must have a factor less than or equal to its square root.

Step 6: Find the Most Frequent Prime After collecting all prime frequencies:

• Initialize ans = -1 (default return value) and mx = 0 (maximum frequency)
• Iterate through the counter items (v, x) where v is the prime and x is its frequency
• If frequency x is greater than mx, update both mx and ans
• If frequency equals mx, keep the larger prime: ans = max(ans, v)

This approach ensures we find all possible prime numbers formed by straight-line traversals and correctly identify the most frequent one, with ties broken by choosing the largest value.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3x3 matrix:

mat = [[1, 9, 7],
       [3, 1, 3],
       [2, 3, 1]]

Step 1: Start from cell (0,0) with value 1

Let's explore the East direction (a=0, b=1):

• Start with v = 1 (not prime, not > 10)
• Move to (0,1): v = 1*10 + 9 = 19
  • Check: 19 > 10? Yes. Is 19 prime? Yes (not divisible by 2,3,4)
  • Add to counter: {19: 1}
• Move to (0,2): v = 19*10 + 7 = 197
  • Check: 197 > 10? Yes. Is 197 prime? Yes
  • Add to counter: {19: 1, 197: 1}
• Can't move further (out of bounds)

Now explore South-East direction (a=1, b=1) from (0,0):

• Start with v = 1
• Move to (1,1): v = 1*10 + 1 = 11
  • Check: 11 > 10? Yes. Is 11 prime? Yes
  • Add to counter: {19: 1, 197: 1, 11: 1}
• Move to (2,2): v = 11*10 + 1 = 111
  • Check: 111 > 10? Yes. Is 111 prime? No (111 = 3 × 37)
  • Not added to counter

Step 2: Start from cell (0,1) with value 9

Let's explore South direction (a=1, b=0):

• Start with v = 9
• Move to (1,1): v = 9*10 + 1 = 91
  • Check: 91 > 10? Yes. Is 91 prime? No (91 = 7 × 13)
• Move to (2,1): v = 91*10 + 3 = 913
  • Check: 913 > 10? Yes. Is 913 prime? No (913 = 11 × 83)

Step 3: Continue for all cells and directions

After checking all starting positions and directions, let's say we found:

• 19 appears 2 times (from different starting points/directions)
• 11 appears 3 times
• 197 appears 1 time
• 31 appears 2 times
• 13 appears 4 times

Step 4: Find the most frequent prime

Scanning through our counter:

• 13 has frequency 4 (highest)
• No other prime has frequency 4

Therefore, the answer is 13.

If we had a tie (e.g., both 13 and 31 appeared 4 times), we would return 31 as it's larger.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × max(m, n) × 10^(max(m, n)/2))

The analysis breaks down as follows:

• The outer two loops iterate through all cells in the matrix: O(m × n)
• For each cell, we explore 8 directions (excluding the case where both a and b are 0): O(8) = O(1)
• In each direction, we traverse at most max(m, n) cells before going out of bounds: O(max(m, n))
• For each number formed during traversal, we check if it's prime using the is_prime function
• The largest number that can be formed has at most max(m, n) digits, making it at most 10^max(m, n)
• The is_prime function runs in O(sqrt(v)) time, where v is the value being checked
• For a number with max(m, n) digits, sqrt(10^max(m, n)) = 10^(max(m, n)/2)

Therefore, the overall time complexity is O(m × n × max(m, n) × 10^(max(m, n)/2)).

Space Complexity: O(m × n × max(m, n))

The space complexity is dominated by the Counter object cnt, which stores the frequency of prime numbers found:

• From each starting cell, we can explore 8 directions
• In each direction, we can form at most max(m, n) - 1 different numbers (excluding single digits)
• With m × n starting cells, the maximum number of unique prime numbers that could be stored is O(m × n × max(m, n))

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

Common Pitfalls

1. Not Counting Intermediate Numbers During Traversal

A critical mistake is only counting the final number at the end of a traversal, rather than counting all numbers formed along the way.

Incorrect approach:

# Wrong: Only counts the final number after traversing to boundary
while 0 <= current_row < rows and 0 <= current_col < cols:
    number = number * 10 + mat[current_row][current_col]
    current_row += row_delta
    current_col += col_delta
# Only check once after loop ends
if number > 10 and is_prime(number):
    prime_frequency[number] = prime_frequency.get(number, 0) + 1

Correct approach:

# Right: Check and count every number formed during traversal
while 0 <= current_row < rows and 0 <= current_col < cols:
    number = number * 10 + mat[current_row][current_col]
    # Check immediately after forming each new number
    if number > 10 and is_prime(number):
        prime_frequency[number] = prime_frequency.get(number, 0) + 1
    current_row += row_delta
    current_col += col_delta

2. Forgetting to Check Single-Digit Starting Numbers

Some implementations might skip checking if the starting cell itself forms a valid prime when combined with the next cell.

Incorrect approach:

# Wrong: Starts with empty number and skips first cell's contribution
number = 0  # Starting with 0 instead of mat[start_row][start_col]
current_row = start_row + row_delta
current_col = start_col + col_delta

Correct approach:

# Right: Start with the digit from the starting cell
number = mat[start_row][start_col]
current_row = start_row + row_delta
current_col = start_col + col_delta

3. Inefficient Prime Checking

Using a naive prime check that tests all numbers up to n-1 can cause timeouts for large numbers.

Inefficient approach:

def is_prime(num):
    if num <= 1:
        return False
    # Wrong: Checking all numbers up to num-1
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

Efficient approach:

def is_prime(num):
    if num <= 1:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    # Right: Only check up to square root
    return all(num % divisor != 0 for divisor in range(3, int(num**0.5) + 1, 2))

4. Integer Overflow with Large Numbers

When traversing long paths, numbers can grow exponentially (e.g., a 10x10 matrix could create numbers with up to 10 digits). While Python handles big integers automatically, other languages might face overflow issues.

Solution for languages with integer limits:

• Add a maximum digit limit check
• Stop traversing when the number exceeds a reasonable threshold
• Use appropriate data types (long long in C++, BigInteger in Java)

# Add safeguard against extremely large numbers
MAX_DIGITS = 10  # or any reasonable limit
while 0 <= current_row < rows and 0 <= current_col < cols:
    number = number * 10 + mat[current_row][current_col]
    if len(str(number)) > MAX_DIGITS:
        break  # Stop if number gets too large
    if number > 10 and is_prime(number):
        prime_frequency[number] = prime_frequency.get(number, 0) + 1