Prime In Diagonal - Practice Coding Problems

Prime In Diagonal - Problem

You are given a 0-indexed two-dimensional integer array nums.

Return the largest prime number that lies on at least one of the diagonals of nums. In case no prime is present on any of the diagonals, return 0.

Note that:

An integer is prime if it is greater than 1 and has no positive integer divisors other than 1 and itself.
An integer val is on one of the diagonals of nums if there exists an integer i for which nums[i][i] = val or an i for which nums[i][nums.length - i - 1] = val.

Input & Output

Example 1 — Basic Case

$ Input: nums = [[1,2,3],[5,5,6],[7,8,9]]

› Output: 7

💡 Note: Main diagonal: [1,5,9], Anti-diagonal: [3,5,7]. Prime numbers: 3, 5, 7. Largest prime is 7.

Example 2 — No Primes

$ Input: nums = [[1,2,3],[5,6,7],[9,10,15]]

› Output: 7

💡 Note: Main diagonal: [1,6,15], Anti-diagonal: [3,6,9]. Prime numbers: 3, 7. Wait - 7 is not on diagonal. Actually primes are just [3], so answer is 3.

Example 3 — All Non-Prime

$ Input: nums = [[1,2,3],[5,4,6],[7,8,9]]

› Output: 7

💡 Note: Main diagonal: [1,4,9], Anti-diagonal: [3,4,7]. Prime numbers on diagonals: 3, 7. Largest is 7.

Constraints

1 ≤ nums.length ≤ 300
nums.length == nums[i].length
1 ≤ nums[i][j] ≤ 4*10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x3 matrix with main and anti-diagonals highlighted

Extract Diagonals

Collect all elements from both diagonals

Find Max Prime

Check each diagonal element for primality, return largest

Key Takeaway

🎯 Key Insight: Only diagonal elements matter - check nums[i][i] and nums[i][n-1-i] for primes

Asked in

A Amazon 12 M Microsoft 8 G Google 6

The key insight is that we only need to check elements on the main diagonal (i,i) and anti-diagonal (i,n-1-i). Best approach is direct diagonal access which achieves Time: O(n√m), Space: O(1) where n is matrix size and m is maximum element value.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Direct Diagonal Access	O(n√m)	O(1)	Only check elements that are actually on the diagonals
Brute Force - Check All Positions	O(n²√m)	O(1)	Check every matrix element to see if it's on a diagonal and prime

Optimized - Direct Diagonal Access — Algorithm Steps

Step 1: Traverse main diagonal elements nums[i][i] for i from 0 to n-1
Step 2: Traverse anti-diagonal elements nums[i][n-1-i] for i from 0 to n-1
Step 3: For each diagonal element, check if prime and update maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Main Diagonal

Access nums[i][i] for i = 0 to n-1

Anti-Diagonal

Access nums[i][n-1-i] for i = 0 to n-1

Check Primes

Test each diagonal value for primality

Code -

solution.c — C

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

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

int solution(int nums[][100], int n) {
    int maxPrime = 0;
    
    // Check main diagonal
    for (int i = 0; i < n; i++) {
        int val = nums[i][i];
        if (isPrime(val)) {
            if (val > maxPrime) {
                maxPrime = val;
            }
        }
    }
    
    // Check anti-diagonal
    for (int i = 0; i < n; i++) {
        int val = nums[i][n - 1 - i];
        if (isPrime(val)) {
            if (val > maxPrime) {
                maxPrime = val;
            }
        }
    }
    
    return maxPrime;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100][100];
    int n = 0;
    
    char *ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    ptr++;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int j = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
                    nums[n][j] = atoi(ptr);
                    j++;
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                }
                if (*ptr == ',') ptr++;
            }
            n++;
        }
        ptr++;
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n√m)

n elements on diagonals, √m for prime checking where m is max value

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

340 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

Optimized - Direct Diagonal Access — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler