Prime In Diagonal

Difficulty: Easy | Acceptance: 37.70% | Paid: No Topics: Array, Math, Matrix, Number Theory

You are given a 0-indexed 2D integer array nums of size n x n, where n is the length of nums.

A number x is considered “prime” if it has exactly two positive divisors: 1 and x. Note that 1 is not a prime number.

Return the largest prime number that lies on at least one of the diagonals of nums. If no such integer exists, return -1.

• Examples
• Constraints
• Approach 1: Iteration with Basic Primality Test
• Approach 2: Sieve of Eratosthenes
• Approach 3: Optimized Primality Test (6k ± 1)

Examples

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*10^6

Approach 1: Iteration with Basic Primality Test

Intuition Iterate through the matrix, identify elements on the main diagonal (where row index equals column index) and the anti-diagonal (where row index plus column index equals n-1), and check if they are prime using a standard trial division method.

Steps

• Iterate through each row index i from 0 to n-1.
• Check the element at nums[i][i] (main diagonal). If it is prime, update the maximum prime found.
• Check the element at nums[i][n-1-i] (anti-diagonal). If it is prime, update the maximum prime found.
• Return the maximum prime found, or -1 if none exist.

from typing import List

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        def is_prime(n: int) -> bool:
            if n < 2:
                return False
            for i in range(2, int(n**0.5) + 1):
                if n % i == 0:
                    return False
            return True

        n = len(nums)
        max_prime = 0
        for i in range(n):
            if is_prime(nums[i][i]):
                max_prime = max(max_prime, nums[i][i])
            if is_prime(nums[i][n - 1 - i]):
                max_prime = max(max_prime, nums[i][n - 1 - i])
        return max_prime if max_prime > 0 else -1

Complexity

• Time: O(n * √M), where n is the size of the matrix and M is the maximum value in the matrix. We iterate through 2n elements, and for each, we perform a primality test up to the square root of the value.
• Space: O(1), as we only use a few variables for storage.
• Notes: This is the most straightforward approach and is efficient enough given the constraints (M ≤ 10⁵).

Approach 2: Sieve of Eratosthenes

Intuition Precompute all prime numbers up to the maximum value present in the matrix using the Sieve of Eratosthenes. This allows for O(1) primality checks for each diagonal element.

Steps

• Find the maximum value max_val in the matrix.
• Create a boolean array is_prime of size max_val + 1 initialized to true.
• Apply the Sieve of Eratosthenes algorithm to mark non-prime indices as false.
• Iterate through the diagonals. For each element, check is_prime[element] and update the maximum prime if true.

from typing import List

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        n = len(nums)
        max_val = 0
        for row in nums:
            for val in row:
                if val > max_val:
                    max_val = val
        
        is_prime = [True] * (max_val + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(max_val**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, max_val + 1, i):
                    is_prime[j] = False
        
        max_prime = 0
        for i in range(n):
            if is_prime[nums[i][i]]:
                max_prime = max(max_prime, nums[i][i])
            if is_prime[nums[i][n - 1 - i]]:
                max_prime = max(max_prime, nums[i][n - 1 - i])
        return max_prime if max_prime > 0 else -1

Complexity

• Time: O(M log log M + n²), where M is the maximum value in the matrix. The Sieve takes O(M log log M), and finding the max value takes O(n²).
• Space: O(M), to store the boolean array of prime flags.
• Notes: This approach is beneficial if there are many primality checks to perform, but for a single pass through 2n elements, the overhead of the sieve might be higher than simple trial division.

Approach 3: Optimized Primality Test (6k ± 1)

Intuition Optimize the primality test by skipping multiples of 2 and 3. All primes greater than 3 are of the form 6k ± 1. This reduces the number of iterations in the loop.

Steps

• Iterate through the matrix diagonals.
• For each number, check if it is less than 2 (not prime), equal to 2 or 3 (prime), or divisible by 2 or 3 (not prime).
• If not, iterate from 5 up to the square root of the number, checking divisibility by i and i + 2 (incrementing i by 6 each time).
• Update the maximum prime found.

from typing import List

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        def is_prime(n: int) -> bool:
            if n <= 1:
                return False
            if n <= 3:
                return True
            if n % 2 == 0 or n % 3 == 0:
                return False
            i = 5
            while i * i <= n:
                if n % i == 0 or n % (i + 2) == 0:
                    return False
                i += 6
            return True

        n = len(nums)
        max_prime = 0
        for i in range(n):
            if is_prime(nums[i][i]):
                max_prime = max(max_prime, nums[i][i])
            if is_prime(nums[i][n - 1 - i]):
                max_prime = max(max_prime, nums[i][n - 1 - i])
        return max_prime if max_prime > 0 else -1

Complexity

• Time: O(n * √M), where n is the size of the matrix and M is the maximum value. The constant factor is lower than the basic trial division because we check fewer divisors.
• Space: O(1), using only a few variables.
• Notes: This is a highly optimized single-number primality test that is very efficient for the given constraints.