LeetCode 3044 - Most Frequent Prime

The problem asks us to traverse a m x n integer matrix and generate numbers by moving in straight lines along eight possible directions: east, south-east, south, south-west, west, north-west, north, and north-east.

leetcodemediumarrayhash-tablemathmatrixcountingenumerationnumber-theory

LeetCode Problem 3044

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Matrix, Counting, Enumeration, Number Theory

Solution

Problem Understanding

The problem asks us to traverse a m x n integer matrix and generate numbers by moving in straight lines along eight possible directions: east, south-east, south, south-west, west, north-west, north, and north-east. Starting from any cell, we can append the digits along a chosen path to form numbers. Importantly, numbers are generated at each step along the path, so if we move through cells containing digits [1, 9, 1], we generate 1, 19, and 191.

The goal is to identify the most frequent prime number greater than 10 among all numbers generated across the matrix. If multiple primes share the maximum frequency, we return the largest. If no prime greater than 10 exists, we return -1.

The input matrix has small dimensions (1 <= m, n <= 6) and digits range from 1 to 9. This means while the total number of numbers generated could be large due to combinatorial paths, the actual numeric values remain manageable since numbers are formed from digits 1 to 9.

Edge cases include single-cell matrices (where no number > 10 may exist), matrices where all numbers are non-prime, or matrices with ties in frequency where the largest prime must be chosen.

Approaches

Brute Force

The brute force approach involves iterating over each cell in the matrix and for each of the eight directions, generating all numbers along that path. For each number, we check if it is greater than 10 and if it is prime. We then count the frequency of each prime number using a hash map and return the most frequent (largest in case of tie).

This approach is correct, but it may be slow due to redundant prime checks and the combinatorial growth of numbers formed from each cell in all directions. With matrix size up to 6x6 and eight directions, the number of potential numbers can grow exponentially, especially since numbers increase as digits are appended.

Optimal Approach

The optimal solution leverages two insights. First, we precompute all prime numbers up to the largest number that can appear in the matrix (which is manageable given the small matrix size). Second, we traverse each cell in each direction once, dynamically generating numbers and immediately counting primes. By doing this, we avoid recomputation and redundant prime checks, improving efficiency. Given the matrix constraints, this method is fast enough.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * max_path_length * sqrt(max_number)) O(#primes) Generate all numbers and check primes on the fly
Optimal O(m * n * max_path_length) O(#primes + #numbers) Precompute primes, count during traversal, avoid redundant checks

Algorithm Walkthrough

  1. Define the eight possible directions using row and column offsets. This allows moving in any straight line from a cell.
  2. Implement a prime checking function that returns True if a number is prime. Optimize by checking divisibility only up to the square root of the number.
  3. Initialize a frequency map (hash map) to store counts of prime numbers.
  4. Iterate over every cell (i, j) in the matrix.
  5. For each cell, iterate over the eight directions.
  6. From each cell and direction, form numbers by appending digits step by step. For each intermediate number:
  • Skip numbers ≤ 10.
  • Check if it is prime.
  • If prime, increment its count in the frequency map.
  1. After processing all cells and directions, identify the prime with the highest frequency. In case of a tie, choose the largest prime.
  2. If no prime > 10 exists, return -1.

Why it works: By traversing all cells in all directions and dynamically checking primes while counting their occurrences, the algorithm guarantees that all candidate numbers are considered and the most frequent prime is correctly identified.

Python Solution

from typing import List
from collections import defaultdict
import math

class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
        def is_prime(n: int) -> bool:
            if n < 2:
                return False
            for i in range(2, int(math.isqrt(n)) + 1):
                if n % i == 0:
                    return False
            return True

        directions = [
            (0, 1), (1, 1), (1, 0), (1, -1),
            (0, -1), (-1, -1), (-1, 0), (-1, 1)
        ]
        
        m, n = len(mat), len(mat[0])
        freq = defaultdict(int)

        for i in range(m):
            for j in range(n):
                for dr, dc in directions:
                    num = 0
                    r, c = i, j
                    while 0 <= r < m and 0 <= c < n:
                        num = num * 10 + mat[r][c]
                        if num > 10 and is_prime(num):
                            freq[num] += 1
                        r += dr
                        c += dc

        if not freq:
            return -1

        max_freq = max(freq.values())
        candidates = [num for num, f in freq.items() if f == max_freq]
        return max(candidates)

The Python solution defines a helper function for prime checking, iterates through all directions from each cell, and counts primes dynamically. The use of a defaultdict simplifies frequency counting. Finally, it selects the most frequent prime or the largest in case of a tie.

Go Solution

package main

func isPrime(n int) bool {
	if n < 2 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func mostFrequentPrime(mat [][]int) int {
	directions := [8][2]int{
		{0, 1}, {1, 1}, {1, 0}, {1, -1},
		{0, -1}, {-1, -1}, {-1, 0}, {-1, 1},
	}
	m, n := len(mat), len(mat[0])
	freq := make(map[int]int)

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for _, dir := range directions {
				num := 0
				r, c := i, j
				for r >= 0 && r < m && c >= 0 && c < n {
					num = num*10 + mat[r][c]
					if num > 10 && isPrime(num) {
						freq[num]++
					}
					r += dir[0]
					c += dir[1]
				}
			}
		}
	}

	if len(freq) == 0 {
		return -1
	}

	maxFreq := 0
	result := -1
	for num, f := range freq {
		if f > maxFreq || (f == maxFreq && num > result) {
			maxFreq = f
			result = num
		}
	}
	return result
}

In Go, we handle frequencies using a map[int]int. We loop over the matrix and directions, generating numbers dynamically. The logic mirrors Python, but type safety and explicit map initialization are Go-specific considerations.

Worked Examples

Example 1: [[1,1],[9,9],[1,1]]

From (0,0):

  • East: 11 → prime, freq 1
  • South-East: 19 → prime, freq 1
  • South: 19, 191 → both prime, freq 19: 2, 191:1

From (0,1):

  • Generates 19, 191, 19, 11 → update frequencies

Continue for all cells. After counting, the highest frequency prime is 19.

Example 2: [[7]]

Only number formed is 7, which is prime but ≤ 10. Return -1.

Example 3: [[9,7,8],[4,6,5],[2,8,6]]

After generating numbers in all directions from all cells and counting primes > 10, 97 emerges as the most frequent prime.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * max(m, n) * sqrt(k)) Traverse each cell and direction. For each number, prime check takes up to sqrt(k), where k is the number size
Space O(#primes) Store counts of prime numbers generated

Given m,n <= 6, max(m,n) = 6. The number of generated numbers is bounded by a few hundred, making this approach efficient.

Test Cases

# Provided examples
assert Solution().mostFrequentPrime([[1,1],[9,9],[1,1]]) == 19  # Most frequent prime is 19
assert Solution().mostFrequentPrime([[7]]) == -1  # Only number is <= 10
assert Solution().mostFrequentPrime([[9,7,8],[4,6,5],[2,8,6]]) == 97  # Most frequent prime is 97

# Edge cases
assert Solution().mostFrequentPrime([[2,3],[5,7]])