Problem

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

Return _the largestprime 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.

$$ \Huge \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \\ \hline \end{array} $$

In the above diagram, one diagonal is [1,5,9] and another diagonal is [3,5,7].

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|} \hline 1 & 2 & \colorbox{YellowOrange}3 \\ \hline 5 & 6 & 7 \\ \hline 9 & 10 & \colorbox{YellowOrange}11 \\ \hline \end{array} $$

1
2
3

Input: nums = [[1,2,3],[5,6,7],[9,10,11]]
Output: 11
Explanation: The numbers 1, 3, 6, 9, and 11 are the only numbers present on at least one of the diagonals. Highlighted cells are the diagonal primes (3 and 11). Since 11 is the largest prime, we return 11.

Example 2

$$ \Huge \begin{array}{|c|c|c|} \hline 1 & 2 & \colorbox{YellowOrange}3 \\ \hline 5 & \colorbox{YellowOrange}17 & 7 \\ \hline 9 & 11 & 10 \\ \hline \end{array} $$

1
2
3

Input: nums = [[1,2,3],[5,17,7],[9,11,10]]
Output: 17
Explanation: The numbers 1, 3, 9, 10, and 17 are all present on at least one of the diagonals. Highlighted cells are the diagonal primes (3 and 17). 17 is the largest prime, so we return 17.

Constraints

  • 1 <= nums.length <= 300
  • nums.length == numsi.length
  • 1 <= nums[i][j] <= 4*106

Solution

Method 1 - Diagonal Primes (Trial Division)

Intuition

We need to find the largest prime number on either diagonal of a square matrix. Since the matrix nums can be up to n x n and values up to 4*10^6, we can check each diagonal value and test for primality (trial division up to sqrt(x)) efficiently.

Approach

  1. Collect all numbers on the main and anti-diagonal (avoid double-counting the center if n is odd).
  2. For each number x, check if it is prime (trial division up to sqrt(x)).
  3. Return the largest such prime, or 0 if none.

Complexity

  • ⏰ Time complexity: O(n * sqrt(M)), where n is the matrix size and M is the largest value in the matrix (up to 4*10^6).
  • 🧺 Space complexity: O(1) (ignoring input and output).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool isPrime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int i = 3; i * i <= x; i += 2) {
        if (x % i == 0) return false;
    }
    return true;
}
int diagonalPrime(vector<vector<int>>& nums) {
    int n = nums.size(), ans = 0;
    for (int i = 0; i < n; ++i) {
        if (isPrime(nums[i][i])) ans = max(ans, nums[i][i]);
        if (isPrime(nums[i][n-i-1])) ans = max(ans, nums[i][n-i-1]);
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import "math"
func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    if x == 2 {
        return true
    }
    if x%2 == 0 {
        return false
    }
    for i := 3; i*i <= x; i += 2 {
        if x%i == 0 {
            return false
        }
    }
    return true
}
func diagonalPrime(nums [][]int) int {
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        if isPrime(nums[i][i]) && nums[i][i] > ans {
            ans = nums[i][i]
        }
        if isPrime(nums[i][n-i-1]) && nums[i][n-i-1] > ans {
            ans = nums[i][n-i-1]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }
    public int diagonalPrime(int[][] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (isPrime(nums[i][i])) ans = Math.max(ans, nums[i][i]);
            if (isPrime(nums[i][n-i-1])) ans = Math.max(ans, nums[i][n-i-1]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

fun isPrime(x: Int): Boolean {
    if (x < 2) return false
    if (x == 2) return true
    if (x % 2 == 0) return false
    var i = 3
    while (i * i <= x) {
        if (x % i == 0) return false
        i += 2
    }
    return true
}
fun diagonalPrime(nums: Array<IntArray>): Int {
    val n = nums.size
    var ans = 0
    for (i in 0 until n) {
        if (isPrime(nums[i][i])) ans = maxOf(ans, nums[i][i])
        if (isPrime(nums[i][n-i-1])) ans = maxOf(ans, nums[i][n-i-1])
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from typing import List
def is_prime(x: int) -> bool:
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 2
    return True

def diagonalPrime(nums: List[List[int]]) -> int:
    n = len(nums)
    ans = 0
    for i in range(n):
        if is_prime(nums[i][i]):
            ans = max(ans, nums[i][i])
        if is_prime(nums[i][n-i-1]):
            ans = max(ans, nums[i][n-i-1])
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

fn is_prime(x: i32) -> bool {
    if x < 2 {
        return false;
    }
    if x == 2 {
        return true;
    }
    if x % 2 == 0 {
        return false;
    }
    let mut i = 3;
    while i * i <= x {
        if x % i == 0 {
            return false;
        }
        i += 2;
    }
    true
}
fn diagonal_prime(nums: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();
    let mut ans = 0;
    for i in 0..n {
        if is_prime(nums[i][i]) && nums[i][i] > ans {
            ans = nums[i][i];
        }
        if is_prime(nums[i][n-i-1]) && nums[i][n-i-1] > ans {
            ans = nums[i][n-i-1];
        }
    }
    ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

export function diagonalPrime(nums: number[][]): number {
    function isPrime(x: number): boolean {
        if (x < 2) return false;
        if (x === 2) return true;
        if (x % 2 === 0) return false;
        for (let i = 3; i * i <= x; i += 2) {
            if (x % i === 0) return false;
        }
        return true;
    }
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (isPrime(nums[i][i])) ans = Math.max(ans, nums[i][i]);
        if (isPrime(nums[i][n-i-1])) ans = Math.max(ans, nums[i][n-i-1]);
    }
    return ans;
}