Skip to main content
Talentd

Most Frequent Prime - Solution & Explanation

MediumArrayHash TableMathMatrix16 min readAsked at: Google
Practice this problem

Problem Statement

You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers in the following way:

  • There could be at most 8 paths from the cells namely: east, south-east, south, south-west, west, north-west, north, and north-east.
  • Select a path from them and append digits in this path to the number being formed by traveling in this direction.
  • Note that numbers are generated at every step, for example, if the digits along the path are 1, 9, 1, then there will be three numbers generated along the way: 1, 19, 191.

Return the most frequent prime number greater than 10 out of all the numbers created by traversing the matrix or -1 if no such prime number exists. If there are multiple prime numbers with the highest frequency, then return the largest among them.

Note: It is invalid to change the direction during the move.

 

Example 1:


Input: mat = [[1,1],[9,9],[1,1]]
Output: 19
Explanation: 
From cell (0,0) there are 3 possible directions and the numbers greater than 10 which can be created in those directions are:
East: [11], South-East: [19], South: [19,191].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [19,191,19,11].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [99,91,91,91,91].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [91,91,99,91,91].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [11,19,191,19].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [11,19,19,191].
The most frequent prime number among all the created numbers is 19.

Example 2:

Input: mat = [[7]]
Output: -1
Explanation: The only number which can be formed is 7. It is a prime number however it is not greater than 10, so return -1.

Example 3:

Input: mat = [[9,7,8],[4,6,5],[2,8,6]]
Output: 97
Explanation: 
Numbers greater than 10 created from the cell (0,0) in all possible directions are: [97,978,96,966,94,942].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [78,75,76,768,74,79].
Numbers greater than 10 created from the cell (0,2) in all possible directions are: [85,856,86,862,87,879].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [46,465,48,42,49,47].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [65,66,68,62,64,69,67,68].
Numbers greater than 10 created from the cell (1,2) in all possible directions are: [56,58,56,564,57,58].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [28,286,24,249,26,268].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [86,82,84,86,867,85].
Numbers greater than 10 created from the cell (2,2) in all possible directions are: [68,682,66,669,65,658].
The most frequent prime number among all the created numbers is 97.

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 6
  • 1 <= mat[i][j] <= 9

Approach Overview

Problem Overview: You are given a matrix of digits. Starting from any cell, build numbers by moving through the grid and concatenating digits along the path. Every number formed is checked for primality, and the task is to return the prime that appears most frequently. If multiple primes have the same frequency, return the largest one.

Approach 1: Depth First Search (DFS) with Path Tracking (O(m * n * k), Space: O(P))

This approach treats the grid like a search space and explores number formations using DFS. From each cell, move in all eight possible directions and keep appending digits to build numbers step by step. Each time a new number is formed, run a primality test and update its frequency in a hash map. The key insight is incremental number construction: instead of recomputing digits each time, multiply the current value by 10 and append the next digit. DFS naturally handles path exploration and ensures all directional sequences are checked. Time complexity is O(m * n * k) where k is the maximum path length, and space complexity is O(P) for storing counts of discovered primes.

This method works well because matrix traversal and incremental number building are efficient. A hash map from the Hash Table category keeps track of prime frequencies. Primality checking relies on basic Number Theory techniques such as checking divisibility up to the square root.

Approach 2: Backtracking Focused on Matrix Paths (O(m * n * k), Space: O(P + k))

Backtracking explores digit sequences similarly but focuses explicitly on matrix paths. Start from each cell and recursively extend the current number while moving in a fixed direction. Each recursive step appends a digit, evaluates whether the new value is prime, and records it in a frequency map. Because the path continues until it exits the grid boundary, recursion depth stays bounded by the grid dimension. Backtracking makes the state transition clear: current position, current number, and chosen direction.

This approach is easier to reason about when modeling the grid as a path-building problem from the Matrix traversal family. The algorithm maintains a global counter for primes and updates the most frequent candidate during traversal. Time complexity remains O(m * n * k) and space complexity is O(P + k), where k represents recursion depth.

Recommended for interviews: The DFS enumeration approach is typically expected. Interviewers want to see that you recognize the grid traversal pattern, generate numbers incrementally, and store frequencies using a hash map. Demonstrating brute enumeration of paths shows problem understanding, but combining traversal with efficient prime checking and counting shows stronger algorithmic skill.

Approach 1: Depth First Search (DFS) with Path Tracking

This approach uses Depth First Search to explore all paths from each cell in the matrix. For each path, we generate numbers by appending digits step-by-step. Then, we check if these numbers are prime and track their frequencies. Finally, we determine the most frequent prime number greater than 10.

The solution uses a recursive DFS function to explore paths from each cell. Each new digit forms and extends numbers by traversing in specified directions, and these paths are checked for prime conditions (>10). The function counts these primes and determines the one with the highest frequency.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(8^(m * n)) - Due to exponential path exploration in recursion.

Space Complexity: O(m * n) for recursion stack and prime tracking.

Try this approach in the editor →

Approach 2: Backtracking Focused on Matrix Paths

This approach introduces backtracking to optimize search in the matrix for prime number paths. For every starting cell, the method attempts all potential valid paths holding a number construct as it explores, abandoning paths prematurely when they're deemed non-promising.

The C++ implementation enhances path exploration by using a backtracking strategy to navigate potential paths of digits forming numbers, checking for primes only when paths gather enough digits. This incremental path decision prevents excessive memory use and focuses computational effort on promising paths.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(8^(m * n)) - Due to potential path exploration.

Space Complexity: O(m * n) for embedding matrix and track past visited configurations.

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

We can use a hash table to count the frequency of each prime number greater than 10.

For each cell, we can start from it, generate a number along one of the 8 directions, and then determine whether the generated number is a prime number greater than 10. If it is, we add it to the hash table.

Finally, we traverse the hash table to find the prime number with the highest frequency. If there are multiple prime numbers with the highest frequency, we return the largest one.

The time complexity is O(m times n times max(m, n) times {10}^{\frac{max(m, n)}{2}}), and the space complexity is O(m times n times max(m, n)). Here, m and n are the number of rows and columns of mat, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth First Search (DFS) with Path Tracking

Time Complexity: O(8^(m * n)) - Due to exponential path exploration in recursion.

Space Complexity: O(m * n) for recursion stack and prime tracking.

Backtracking Focused on Matrix Paths

Time Complexity: O(8^(m * n)) - Due to potential path exploration.

Space Complexity: O(m * n) for embedding matrix and track past visited configurations.

Hash Table + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Path TrackingO(m * n * k)O(P)General case when enumerating all directional number formations in the grid
Backtracking on Matrix PathsO(m * n * k)O(P + k)Useful when modeling the problem explicitly as recursive path exploration

Video Solution

Most Frequent Prime | Leetcode 3044 • Ayushi Sharma • 796 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Most Frequent Prime easy or hard?
Most Frequent Prime is considered a Medium difficulty problem. The challenge comes from combining matrix traversal, incremental number construction, prime checking, and frequency tracking. Candidates comfortable with DFS and hash maps typically solve it without major difficulty.
Most Frequent Prime Python/Java solution
Python and Java implementations usually follow the same pattern: iterate over every grid cell, explore directional paths using DFS or loops, construct numbers incrementally, and store counts in a hash map. A helper function checks whether a number is prime before updating the frequency.
How to solve Most Frequent Prime in O(n)?
A strict O(n) solution is not feasible because the algorithm must explore multiple paths from each cell in the grid. The optimal practical approach is O(m * n * k) using DFS or directional enumeration. Efficient prime checking and incremental number construction keep the runtime manageable.
What is the best approach for Most Frequent Prime?
The most effective approach is DFS-based enumeration from every grid cell while forming numbers incrementally. Each new value is checked for primality and recorded in a hash map. This method systematically explores all valid digit sequences and tracks frequencies efficiently with O(m * n * k) time complexity.
Is Most Frequent Prime asked at Google/Amazon/Meta?
Matrix traversal and number construction problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the underlying patterns—grid traversal, hashing for frequency counting, and prime checking—are common interview topics.
What data structure is used in Most Frequent Prime?
The key data structure is a hash map that stores prime numbers as keys and their frequencies as values. The algorithm also relies on matrix traversal techniques and directional movement across the grid. Prime validation uses basic number theory checks.
What is the time complexity of Most Frequent Prime?
The overall time complexity is O(m * n * k), where m and n are the grid dimensions and k is the maximum length of a path explored in one direction. Each step forms a new number and performs a prime check, typically up to the square root of the number. Space complexity is mainly O(P) for storing prime frequencies.

Ready to solve this problem?

Practice Most Frequent Prime with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays