Prime In Diagonal

Let’s create a solution for finding the largest prime number that lies on at least one of the diagonals of a given two-dimensional array.

Understanding the Problem

We need to find the largest prime number from the elements that are on the diagonals of the given square matrix.

Approach

1. Find Diagonal Elements: Iterate through the main diagonal and the anti-diagonal of the matrix and collect the elements.
2. Check Prime: Write a function to check if a number is prime. We can do this by checking if the number has any divisors other than 1 and itself.
3. Find the Largest Prime: Iterate through the collected elements and find the largest prime number.

Implementation

 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

class Solution:
    def is_prime(self, 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

    def diagonalPrime(self, nums: List[List[int]]) -> int:
        n = len(nums)
        largest_prime = 0

        # Step 1: Iterate through diagonals
        for i in range(n):
            # Main diagonal element
            main_diagonal = nums[i][i]
            # Anti-diagonal element
            anti_diagonal = nums[i][n - i - 1]

            # Step 2: Check if the numbers are prime
            if self.is_prime(main_diagonal):
                largest_prime = max(largest_prime, main_diagonal)
            if self.is_prime(anti_diagonal):
                largest_prime = max(largest_prime, anti_diagonal)

        # Step 3: Return the largest prime
        return largest_prime

Examples

• For nums = [[1,2,3],[5,6,7],[9,10,11]], the largest prime on the diagonals is 11.
• For nums = [[1,2,3],[5,17,7],[9,11,10]], the largest prime on the diagonals is 17.

Complexity

The time complexity of this solution is O(n * sqrt(m)), where n is the size of the matrix, and m is the largest number in the matrix. The space complexity is O(1) since we are only using a constant amount of extra space.