Most Frequent Prime - Practice Coding Problems

Most Frequent Prime - Problem

Array Hash Table Math Matrix Counting Enumeration Number Theory Medium

You are given an m x n 0-indexed 2D matrix mat. From every cell, you can create numbers by traveling in up to 8 directions: east, south-east, south, south-west, west, north-west, north, and north-east.

Select a path from any cell and append digits in this direction to form numbers. Numbers are generated at every step - for example, if digits along a path are 1, 9, 1, then three numbers are generated: 1, 19, and 191.

Return the most frequent prime number greater than 10 from all numbers created, or -1 if no such prime exists. If multiple primes have the highest frequency, return the largest among them.

Note: You cannot change direction during movement along a path.

Input & Output

Example 1 — Basic Matrix

$ Input: mat = [[1,1],[9,9]]

› Output: 11

💡 Note: From cell (0,0): paths generate numbers 1, 11, 19, 99. From other cells we get similar numbers. Prime 11 appears most frequently in various directions.

Example 2 — No Valid Primes

$ Input: mat = [[1]]

› Output: -1

💡 Note: Single cell can only generate number 1, which is not > 10, so no valid primes exist.

Example 3 — Multiple Directions

$ Input: mat = [[7,1,3],[9,7,1],[2,3,1]]

› Output: 13

💡 Note: Various paths generate primes like 71, 13, 37. Prime 13 appears in multiple directions making it most frequent.

Constraints

1 ≤ m, n ≤ 6
1 ≤ mat[i][j] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Matrix Input

2D matrix with single digits

Path Exploration

Generate numbers by moving in 8 directions

Prime Frequency

Count prime numbers > 10 and return most frequent

Key Takeaway

🎯 Key Insight: Generate numbers incrementally in all 8 directions, using efficient prime checking to count frequencies

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to systematically generate all possible numbers by traversing the matrix in all 8 directions from each cell, then efficiently count prime frequencies. Best approach uses optimized prime checking with overflow prevention. Time: O(m × n × max_path × √max_num), Space: O(unique_primes)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Numbers	O(m × n × max_path × √max_num)	O(total_numbers)	Generate all possible numbers from all cells in all directions, check primality, count frequencies
Optimized with Efficient Prime Checking	O(m × n × max_path × √max_num)	O(unique_primes)	Same approach but with optimized prime checking and better number generation

Brute Force - Generate All Numbers — Algorithm Steps

Step 1: For each cell, start paths in all 8 directions
Step 2: Generate numbers incrementally along each path
Step 3: Check primality for numbers > 10 and count frequencies
Step 4: Return most frequent prime (largest if tied)

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from Cell

Begin from each cell in the matrix

Explore 8 Directions

Move in all 8 directions, building numbers

Count Prime Frequencies

Track frequency of each prime > 10

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_PRIMES 10000

struct PrimeCount {
    int prime;
    int count;
};

int isPrime(int num) {
    if (num < 2) return 0;
    if (num == 2) return 1;
    if (num % 2 == 0) return 0;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return 0;
    }
    return 1;
}

void generateNumbers(int** mat, int m, int n, int startR, int startC, struct PrimeCount* primes, int* primeCount) {
    int directions[8][2] = {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};
    
    for (int d = 0; d < 8; d++) {
        int r = startR, c = startC;
        int currentNum = 0;
        
        while (r >= 0 && r < m && c >= 0 && c < n) {
            currentNum = currentNum * 10 + mat[r][c];
            
            if (currentNum > 10 && isPrime(currentNum)) {
                // Find if prime already exists
                int found = -1;
                for (int i = 0; i < *primeCount; i++) {
                    if (primes[i].prime == currentNum) {
                        found = i;
                        break;
                    }
                }
                
                if (found != -1) {
                    primes[found].count++;
                } else {
                    primes[*primeCount].prime = currentNum;
                    primes[*primeCount].count = 1;
                    (*primeCount)++;
                }
            }
            
            r += directions[d][0];
            c += directions[d][1];
        }
    }
}

int solution(int** mat, int m, int n) {
    struct PrimeCount primes[MAX_PRIMES];
    int primeCount = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            generateNumbers(mat, m, n, i, j, primes, &primeCount);
        }
    }
    
    if (primeCount == 0) return -1;
    
    int maxFreq = 0;
    for (int i = 0; i < primeCount; i++) {
        if (primes[i].count > maxFreq) {
            maxFreq = primes[i].count;
        }
    }
    
    int result = -1;
    for (int i = 0; i < primeCount; i++) {
        if (primes[i].count == maxFreq && primes[i].prime > result) {
            result = primes[i].prime;
        }
    }
    return result;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    // Simple parser for 2D array
    int mat[100][100];
    int m = 0, n = 0;
    
    char* ptr = strchr(input, '[') + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                mat[m][n++] = atoi(ptr);
                while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                if (*ptr == ',') ptr++;
            }
            m++;
        }
        ptr++;
    }
    
    // Create dynamic array for solution
    int** matPtr = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        matPtr[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            matPtr[i][j] = mat[i][j];
        }
    }
    
    printf("%d\n", solution(matPtr, m, n));
    
    for (int i = 0; i < m; i++) {
        free(matPtr[i]);
    }
    free(matPtr);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × max_path × √max_num)

For each cell (m×n), explore paths up to max_path length, check primality with √max_num complexity

✓ Linear Growth

Space Complexity

O(total_numbers)

Hash map stores all unique numbers generated with their frequencies

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Numbers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler