LeetCode 2614 - Prime In Diagonal

The problem gives us a square matrix nums of size n x n. We need to examine the values that appear on the two diagonals of the matrix and return the largest value among them that is prime.

leetcodeeasyarraymathmatrixnumber-theory

LeetCode Problem 2614

Difficulty: 🟢 Easy
Topics: Array, Math, Matrix, Number Theory

Solution

Problem Understanding

The problem gives us a square matrix nums of size n x n. We need to examine the values that appear on the two diagonals of the matrix and return the largest value among them that is prime.

There are two diagonals in a square matrix:

  • The primary diagonal contains elements where the row index and column index are the same, nums[i][i]
  • The secondary diagonal contains elements where the column index is n - i - 1, nums[i][n - i - 1]

A number can belong to both diagonals when the matrix has odd size and the element lies in the center.

The task is specifically asking for the largest prime number found on either diagonal. If no diagonal element is prime, the answer should be 0.

A prime number is an integer greater than 1 that is divisible only by 1 and itself. This means values like 1, 0, and negative numbers are not prime.

The matrix size can be as large as 300 x 300, and each value can be as large as 4 * 10^6. These constraints are important because they tell us:

  • We do not need to inspect every element in the matrix, only the diagonal elements
  • There are at most 2 * n diagonal values to check, which is at most 600
  • Prime checking must still be reasonably efficient because values can be large

An important observation is that even though the matrix contains up to 90,000 elements, only diagonal elements matter. This dramatically reduces the amount of work needed.

Several edge cases are important:

  • A matrix may contain no prime numbers on the diagonals
  • The matrix may have size 1 x 1
  • The center element of an odd-sized matrix belongs to both diagonals
  • Large composite numbers may appear and must not be incorrectly classified as prime
  • The largest prime may appear multiple times

Because the input is guaranteed to be square, we do not need to handle malformed dimensions.

Approaches

Brute Force Approach

A straightforward solution would scan every element in the matrix. For each element, we would first determine whether it belongs to either diagonal. If it does, we would check whether it is prime and update the maximum prime found so far.

This approach works because every matrix element is examined, so no diagonal value can be missed. However, it performs unnecessary work because most matrix elements are not on either diagonal.

For an n x n matrix, this method examines all n^2 elements even though only about 2n elements matter.

Optimal Approach

The key observation is that only diagonal elements matter. Instead of scanning the entire matrix, we can directly iterate through indices 0 to n - 1 and access:

  • nums[i][i]
  • nums[i][n - i - 1]

For each of these values, we check whether it is prime. If it is, we update the maximum answer.

The remaining challenge is efficient primality testing. A number x only needs to be tested for divisibility up to sqrt(x). If no divisor exists in that range, the number is prime.

Since there are at most 600 diagonal values and each primality test costs at most O(sqrt(x)), this solution is easily fast enough.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² × √m) O(1) Checks every matrix element unnecessarily
Optimal O(n × √m) O(1) Only processes diagonal elements

Here, n is the matrix dimension and m is the maximum matrix value.

Algorithm Walkthrough

  1. Initialize a variable largest_prime to 0.

This variable stores the best answer found so far. If no prime exists on the diagonals, it will remain 0. 2. Define a helper function is_prime(num).

This function determines whether a number is prime.

  • If num <= 1, return False
  • If num == 2, return True
  • If num is even and greater than 2, return False
  • Otherwise, test divisibility from 3 to sqrt(num) using odd numbers only

Checking only up to sqrt(num) works because if a larger factor exists, a smaller paired factor must also exist. 3. Iterate through all row indices from 0 to n - 1.

For each row index i, access:

  • Primary diagonal value: nums[i][i]
  • Secondary diagonal value: nums[i][n - i - 1]
  1. Check whether each diagonal value is prime.

If a value is prime, compare it with largest_prime and keep the larger value. 5. After processing all diagonal elements, return largest_prime.

Why it works

The algorithm works because every valid diagonal element is visited exactly once per diagonal definition. The primary diagonal covers all nums[i][i], and the secondary diagonal covers all nums[i][n - i - 1]. Any element belonging to a diagonal must satisfy one of these two forms.

The primality test is mathematically correct because every composite number has at least one divisor less than or equal to its square root. Therefore, if no divisor exists in that range, the number must be prime.

Since the algorithm checks every relevant diagonal value and keeps the maximum prime encountered, the final result is guaranteed to be correct.

Python Solution

from typing import List
import math

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        def is_prime(num: int) -> bool:
            if num <= 1:
                return False
            
            if num == 2:
                return True
            
            if num % 2 == 0:
                return False
            
            limit = int(math.sqrt(num))
            
            for divisor in range(3, limit + 1, 2):
                if num % divisor == 0:
                    return False
            
            return True
        
        n = len(nums)
        largest_prime = 0
        
        for i in range(n):
            primary = nums[i][i]
            secondary = nums[i][n - i - 1]
            
            if is_prime(primary):
                largest_prime = max(largest_prime, primary)
            
            if is_prime(secondary):
                largest_prime = max(largest_prime, secondary)
        
        return largest_prime

The implementation starts by defining the helper function is_prime. This function handles small edge cases first, which avoids unnecessary work. Even numbers greater than 2 are immediately rejected because they cannot be prime.

The loop only checks odd divisors because all even divisors were already eliminated. The upper bound is the square root of the number, which keeps the primality check efficient.

The main loop iterates through all diagonal indices. For each index, it extracts both diagonal values directly instead of scanning the entire matrix. Each value is tested for primality, and the maximum prime encountered so far is stored in largest_prime.

Finally, the method returns the result after all diagonal elements have been processed.

Go Solution

package main

import "math"

func diagonalPrime(nums [][]int) int {
	isPrime := func(num int) bool {
		if num <= 1 {
			return false
		}

		if num == 2 {
			return true
		}

		if num%2 == 0 {
			return false
		}

		limit := int(math.Sqrt(float64(num)))

		for divisor := 3; divisor <= limit; divisor += 2 {
			if num%divisor == 0 {
				return false
			}
		}

		return true
	}

	n := len(nums)
	largestPrime := 0

	for i := 0; i < n; i++ {
		primary := nums[i][i]
		secondary := nums[i][n-i-1]

		if isPrime(primary) && primary > largestPrime {
			largestPrime = primary
		}

		if isPrime(secondary) && secondary > largestPrime {
			largestPrime = secondary
		}
	}

	return largestPrime
}

The Go version follows the same algorithmic structure as the Python solution. One notable difference is that Go requires explicit conversion when using math.Sqrt, because it operates on float64.

The solution uses a closure for the isPrime helper function, which keeps the implementation compact and readable.

Go slices are used naturally for the matrix representation, and integer overflow is not a concern because the maximum matrix value is only 4 * 10^6.

Worked Examples

Example 1

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

Primary diagonal:

1, 6, 11

Secondary diagonal:

3, 6, 9

Now trace the algorithm:

i Primary Secondary Prime Values Found largest_prime
0 1 3 3 3
1 6 6 none 3
2 11 9 11 11

Final answer:

11

Example 2

nums = [
    [1, 2, 3],
    [5,17, 7],
    [9,11,10]
]

Primary diagonal:

1, 17, 10

Secondary diagonal:

3, 17, 9

Trace the algorithm:

i Primary Secondary Prime Values Found largest_prime
0 1 3 3 3
1 17 17 17 17
2 10 9 none 17

Final answer:

17

Complexity Analysis

Measure Complexity Explanation
Time O(n × √m) There are at most 2n diagonal elements, each requiring primality testing
Space O(1) Only a few variables are used

Here, n is the matrix size and m is the maximum value inside the matrix.

The algorithm avoids scanning the entire matrix and instead focuses only on the diagonals. Each primality test checks divisibility up to the square root of the number, which is efficient enough for values up to 4 * 10^6.

Because no additional data structures proportional to input size are allocated, the space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        import math

        def is_prime(num: int) -> bool:
            if num <= 1:
                return False
            
            if num == 2:
                return True
            
            if num % 2 == 0:
                return False
            
            limit = int(math.sqrt(num))
            
            for divisor in range(3, limit + 1, 2):
                if num % divisor == 0:
                    return False
            
            return True

        n = len(nums)
        answer = 0

        for i in range(n):
            if is_prime(nums[i][i]):
                answer = max(answer, nums[i][i])

            if is_prime(nums[i][n - i - 1]):
                answer = max(answer, nums[i][n - i - 1])

        return answer

solution = Solution()

assert solution.diagonalPrime([
    [1, 2, 3],
    [5, 6, 7],
    [9,10,11]
]) == 11  # Provided example with prime on primary diagonal

assert solution.diagonalPrime([
    [1, 2, 3],
    [5,17, 7],
    [9,11,10]
]) == 17  # Provided example with center prime

assert solution.diagonalPrime([
    [4, 6],
    [8, 9]
]) == 0  # No primes on diagonals

assert solution.diagonalPrime([
    [2]
]) == 2  # Single-element matrix with prime

assert solution.diagonalPrime([
    [1]
]) == 0  # Single-element matrix with non-prime

assert solution.diagonalPrime([
    [13, 2, 5],
    [4, 11, 6],
    [7, 8, 17]
]) == 17  # Multiple primes on diagonals

assert solution.diagonalPrime([
    [25, 2, 29],
    [4, 15, 6],
    [31, 8, 49]
]) == 31  # Largest prime on secondary diagonal

assert solution.diagonalPrime([
    [999983, 1],
    [1, 999979]
]) == 999983  # Large prime values

assert solution.diagonalPrime([
    [4, 5, 6],
    [7, 8, 11],
    [13,14,15]
]) == 13  # Prime appears only on secondary diagonal
Test Why
Example 1 Verifies basic functionality
Example 2 Verifies center element handling
No primes Ensures correct return value of 0
Single prime element Tests smallest valid matrix
Single non-prime element Tests smallest non-prime case
Multiple diagonal primes Ensures maximum prime is selected
Secondary diagonal maximum Verifies both diagonals are checked
Large prime values Tests primality checking efficiency
Prime only on secondary diagonal Confirms secondary diagonal logic

Edge Cases

Matrix with No Prime Numbers

A matrix may contain only composite numbers or 1 on its diagonals. This is important because a careless implementation might incorrectly treat 1 as prime or return an uninitialized value.

The implementation handles this correctly by initializing the answer to 0 and only updating it when a valid prime is found.

Single Element Matrix

When the matrix size is 1 x 1, the single value belongs to both diagonals simultaneously. A buggy implementation could accidentally mishandle indexing or double-count the value incorrectly.

The algorithm works correctly because both diagonal expressions evaluate to the same index. Even if checked twice, the maximum operation remains correct.

Large Composite Numbers

Values can be as large as 4 * 10^6, so inefficient primality testing could become expensive. Additionally, incorrect divisor logic might falsely classify large composite numbers as prime.

The implementation avoids this by testing divisibility only up to the square root of the number and skipping unnecessary even divisors. This ensures both correctness and efficiency.

Odd-Sized Matrices with Shared Center

In odd-sized matrices, the center element belongs to both diagonals. A naive implementation might attempt to avoid duplicate checks using complicated logic that introduces bugs.

This solution simply checks the value twice if necessary. Since the operation is only a maximum comparison, duplicate processing does not affect correctness and keeps the code simpler.