#2614

Easy

LeetCode Problem Workspace

Prime In Diagonal

Find the largest prime number located on any diagonal of a square matrix using array iteration and prime checking techniques.

array math matrix number theory

Problem Statement

Given a 0-indexed square matrix nums, your task is to find the largest prime number located on at least one of the diagonals. Both the main diagonal and the anti-diagonal should be considered when evaluating which numbers qualify.

Return 0 if no prime number exists along any diagonal. Each number in nums is guaranteed to be a positive integer within the range 1 to 4*10^6, and the matrix size will be between 1 and 300.

Examples

Example 1

Input: nums = [[1,2,3],[5,6,7],[9,10,11]]

Output: 11

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

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 Approach

Iterate Over Diagonals

Traverse both the main and secondary diagonals of the matrix, collecting all numbers that appear on these diagonals. This ensures that no potential prime is missed and aligns with the array plus math pattern.

Check Primality Efficiently

For each number found on a diagonal, apply a primality check using trial division up to the square root. Optimizations like skipping even numbers after 2 reduce unnecessary computations.

Determine Maximum Prime

Compare all primes collected from the diagonals and return the largest one. If the set of primes is empty, return 0. This final step ensures correctness even when no prime exists on any diagonal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * sqrt(m)) where n is the matrix size and m is the maximum element, due to checking primality for each diagonal element. Space complexity is O(n) for storing diagonal numbers temporarily.

What Interviewers Usually Probe

Expect candidates to iterate only over diagonals rather than the full matrix.
Look for optimized primality checks rather than naive looping over all numbers.
Notice if candidates handle the edge case where no prime exists.

Common Pitfalls or Variants

Common pitfalls

Iterating over the entire matrix instead of just the diagonals wastes time.
Checking primality inefficiently can lead to timeouts for large numbers.
Failing to return 0 when no prime exists on the diagonals.

Follow-up variants

Find the smallest prime on any diagonal instead of the largest.
Sum all prime numbers on the diagonals rather than returning the maximum.
Check only the main diagonal for primes and ignore the anti-diagonal.

FAQ

What does 'Prime In Diagonal' specifically require?

It requires finding the largest prime number located on either the main or secondary diagonal of a square matrix.

Can I check the entire matrix instead of just diagonals?

Yes, but it's inefficient. The problem pattern focuses on diagonal iteration to reduce unnecessary computations.

How do I handle matrices with no prime numbers on diagonals?

Return 0 as specified. GhostInterview flags this edge case to prevent overlooked failures.

What is the best way to check primality for numbers up to 4*10^6?

Use trial division up to the square root, skipping even numbers after 2, which is efficient for this range.

Does this problem test Array plus Math skills?

Yes, it combines array traversal for diagonals with number theory for prime checking, matching the exact pattern.

terminal

Solution

Solution 1: Math + Simulation

We implement a function `is_prime` to check whether a number is prime.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#3044 most frequent prime #2607 make k subarray sums equal #2601 prime subtraction operation