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.

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

Examples

Example 1

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. Since 11 is the largest prime, we return 11.

Example 2

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. 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

Intuition

We need to find the largest prime number on either diagonal of a square matrix. Since the matrix can be up to 300x300 and values up to 4*10^6, we can check each diagonal value and test for primality 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, check if it is prime (trial division up to sqrt(x)).
  3. Return the largest such prime, or 0 if none.

Code

C++
 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 * 1LL * 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;
}
Go
 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
}
Java
 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 * 1L * 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;
    }
}
Kotlin
 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
}
Python
 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
Rust
 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
}
TypeScript
 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;
}

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).