# Prime In Diagonal
**Difficulty:** EASY
[External](https://leetcode.com/problems/prime-in-diagonal)
Canonical: https://scaleengineer.com/dsa/problems/prime-in-diagonal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Matrix
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## 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`.

![](https://assets.glich.co/dsa/prime-in-diagonal/image0.png)

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

**Example 1:**

**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:**

**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`

# Approaches
## Brute-Force Primality Test
This approach involves iterating through the two diagonals of the matrix. For each number encountered, a helper function is called to check if it is a prime number. The largest prime found is tracked and returned. The primality test is done in a naive way by checking for divisibility from 2 up to the number itself minus one.
**Time:** O(N * M), where `N` is the side length of the matrix and `M` is the maximum value of an element. For each of the `~2*N` diagonal elements, the primality test takes up to `O(M)` time. · **Space:** O(1) extra space.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to the naive primality test.; Will not pass the time limits for the given constraints, resulting in a 'Time Limit Exceeded' error.
### Explanation
The main logic iterates through the rows of the matrix from `i = 0` to `n-1`, where `n` is the side length of the square matrix. In each iteration, it picks the two diagonal elements: `nums[i][i]` (main diagonal) and `nums[i][n-1-i]` (anti-diagonal). A helper function, `isPrime(num)`, is used to determine primality. This function checks for divisibility by every integer from 2 up to `num - 1`. If a number is found to be prime and is larger than the current maximum prime found, the maximum is updated. The final result is the largest prime number found after checking all diagonal elements.

```java
class Solution {
    private boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int maxPrime = 0;
        for (int i = 0; i < n; i++) {
            // Main diagonal
            int val1 = nums[i][i];
            if (isPrime(val1)) {
                maxPrime = Math.max(maxPrime, val1);
            }
            // Anti-diagonal
            int val2 = nums[i][n - 1 - i];
            if (isPrime(val2)) {
                maxPrime = Math.max(maxPrime, val2);
            }
        }
        return maxPrime;
    }
}
```
### Algorithm
- Initialize a variable `maxPrime` to 0.
- Get the size of the matrix, `n = nums.length`.
- Iterate from `i = 0` to `n-1`.
- Inside the loop, consider the number on the main diagonal: `val1 = nums[i][i]`.
- Check if `val1` is prime using a brute-force helper function `isPrime(val1)`.
- If `isPrime(val1)` is true and `val1 > maxPrime`, update `maxPrime = val1`.
- Consider the number on the anti-diagonal: `val2 = nums[i][n-1-i]`.
- Check if `val2` is prime using `isPrime(val2)`.
- If `isPrime(val2)` is true and `val2 > maxPrime`, update `maxPrime = val2`.
- After the loop finishes, return `maxPrime`.

**`isPrime(num)` (Brute-Force):**
1. If `num <= 1`, return `false`.
2. Iterate from `j = 2` to `num - 1`.
3. If `num % j == 0`, then `num` is not prime, return `false`.
4. If the loop completes, `num` is prime, return `true`.

## Pre-computation with Sieve of Eratosthenes
This method improves performance by pre-computing all prime numbers up to the maximum possible value in the input matrix (`4*10^6`). It uses the Sieve of Eratosthenes algorithm to create a lookup table (a boolean array) indicating whether each number is prime. This allows for constant-time primality checks for the diagonal elements.
**Time:** O(M log log M + N), where `M` is the maximum value and `N` is the matrix side length. The sieve creation `O(M log log M)` dominates the runtime. The subsequent traversal of the diagonal is `O(N)`. · **Space:** O(M), where `M` is the maximum possible value of a number (`4*10^6`). This is required to store the sieve array.
**Pros:** Very fast primality checks (`O(1)`) after the initial setup.; Efficient if many primality tests are needed on numbers within the pre-computed range.
**Cons:** Uses significant memory (`O(M)`) to store the sieve.; The one-time cost of building the sieve can be higher than performing individual checks if the number of checks is small.; For the given constraints, this approach is slightly less time-efficient than the optimized trial division method.
### Explanation
First, we determine the upper bound for the numbers, which is `M = 4*10^6`. We create a boolean array `sieve` of size `M+1`. `sieve[i]` will be `true` if `i` is prime, and `false` otherwise. The Sieve of Eratosthenes algorithm is applied to populate this array. After the sieve is built, we iterate through the diagonals of the `nums` matrix. For each diagonal number `val`, we can now check if it's prime in `O(1)` time by looking up `sieve[val]`. We keep track of the largest prime found and return it.

```java
import java.util.Arrays;

class Solution {
    private static final int MAX_VAL = 4000001;
    private static boolean[] isPrime = new boolean[MAX_VAL];

    // Static block to pre-compute primes using Sieve
    static {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p < MAX_VAL; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i < MAX_VAL; i += p) {
                    isPrime[i] = false;
                }
            }
        }
    }

    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int maxPrime = 0;
        for (int i = 0; i < n; i++) {
            // Main diagonal
            int val1 = nums[i][i];
            if (isPrime[val1]) {
                maxPrime = Math.max(maxPrime, val1);
            }
            // Anti-diagonal
            int val2 = nums[i][n - 1 - i];
            if (isPrime[val2]) {
                maxPrime = Math.max(maxPrime, val2);
            }
        }
        return maxPrime;
    }
}
```
### Algorithm
- Create a boolean array `isPrime` up to `4*10^6 + 1`.
- Populate the array using the Sieve of Eratosthenes algorithm. This involves marking all numbers as potentially prime, then iterating from 2 and marking all multiples of each prime number as not prime.
- Initialize `maxPrime = 0`.
- Iterate `i` from `0` to `n-1`.
- Check `nums[i][i]`: If `isPrime[nums[i][i]]` is true, update `maxPrime = Math.max(maxPrime, nums[i][i])`.
- Check `nums[i][n-1-i]`: If `isPrime[nums[i][n-1-i]]` is true, update `maxPrime = Math.max(maxPrime, nums[i][n-1-i])`.
- Return `maxPrime`.

## Optimized Trial Division
This is a significant improvement over the brute-force method and the most efficient approach for the given constraints. It uses an optimized helper function to check for primality. The key optimization is that instead of checking for divisors up to `n-1`, it only checks up to the square root of `n`, which is mathematically sufficient.
**Time:** O(N * sqrt(M)), where `N` is the side length of the matrix and `M` is the maximum value of an element. For each of the `~2*N` diagonal elements, the primality test takes `O(sqrt(M))` time. This is the most time-efficient solution for the given constraints. · **Space:** O(1) extra space.
**Pros:** Excellent balance of time and space efficiency.; Fast enough for the given constraints.; Uses minimal memory (`O(1)`).; Simpler to implement than the Sieve approach.
**Cons:** Can be slower than a pre-computation approach if a very large number of primality tests were needed, but for this problem's constraints, it is the most efficient.
### Explanation
The overall structure remains the same: iterate through the diagonals and check each number. The key improvement is in the `isPrime(num)` helper function. A number `num` is not prime if it has a divisor `d` such that `1 < d < num`. If such a divisor exists, there must be one that is less than or equal to `sqrt(num)`. Therefore, the `isPrime` function only needs to check for divisibility by integers from 2 up to `sqrt(num)`. This drastically reduces the number of operations for the primality test, making the overall solution very efficient.

```java
class Solution {
    private boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        // Check for divisors only up to the square root of n.
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int maxPrime = 0;
        for (int i = 0; i < n; i++) {
            // Main diagonal
            int val1 = nums[i][i];
            if (isPrime(val1)) {
                maxPrime = Math.max(maxPrime, val1);
            }
            // Anti-diagonal
            // Note: if i == n-1-i, we check the same element twice, which is fine.
            int val2 = nums[i][n - 1 - i];
            if (isPrime(val2)) {
                maxPrime = Math.max(maxPrime, val2);
            }
        }
        return maxPrime;
    }
}
```
### Algorithm
- Initialize `maxPrime = 0`.
- Iterate `i` from `0` to `n-1`.
- Check `nums[i][i]`: If it's a prime (using the optimized method) and greater than `maxPrime`, update `maxPrime`.
- Check `nums[i][n-1-i]`: If it's a prime and greater than `maxPrime`, update `maxPrime`.
- Return `maxPrime`.

**`isPrime(num)` (Optimized):**
1. If `num <= 1`, return `false`.
2. For `d` from `2` to `sqrt(num)`: if `num % d == 0`, return `false`.
3. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  int diagonalPrime(int[][] nums) {
    int n = nums.length;
    int 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;
  }
private
  boolean isPrime(int x) {
    if (x < 2) {
      return false;
    }
    for (int i = 2; i <= x / i; ++i) {
      if (x % i == 0) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} nums * @return {number} */ var diagonalPrime = function ( nums ) { let ans = 0 ; const n = nums . length ; 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 ; }; function isPrime ( x ) { if ( x < 2 ) { return false ; } for ( let i = 2 ; i * i <= x ; i ++ ) { if ( x % i === 0 ) { return false ; } } return true ; }
```

### CPP

```cpp
class Solution {
public:
  int diagonalPrime(vector<vector<int>> &nums) {
    int n = nums.size();
    int 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;
  }
  bool isPrime(int x) {
    if (x < 2) {
      return false;
    }
    for (int i = 2; i <= x / i; ++i) {
      if (x % i == 0) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int: def is_prime(x: int) -> bool: if x < 2: return False return all(x % i for i in range(2, int(sqrt(x)) + 1)) n = len(nums) ans = 0 for i, row in enumerate(nums): if is_prime(row[i]): ans = max(ans, row[i]) if is_prime(row[n - i - 1]): ans = max(ans, row[n - i - 1]) return ans

```