2614. Prime In Diagonal Solution & Explanation

Q: Is Prime In Diagonal easy or hard?

Prime In Diagonal is categorized as an Easy problem on LeetCode. The logic involves straightforward diagonal traversal and basic prime checking. The challenge mainly lies in implementing an efficient primality test and recognizing that only diagonal elements matter.

Q: Prime In Diagonal Python/Java solution

Python and Java implementations typically iterate from i = 0 to n-1 and check nums[i][i] and nums[i][n-1-i]. A helper function determines if a number is prime using a square-root loop. The largest prime encountered during the scan is returned.

Q: How to solve Prime In Diagonal in O(n)?

Achieving near O(n) after preprocessing is possible by using the Sieve of Eratosthenes. Precompute primes up to the maximum diagonal value in O(M log log M). After that, checking whether each diagonal element is prime becomes O(1), so the scan of the matrix diagonals takes O(n).

Q: What is the best approach for Prime In Diagonal?

The most practical approach is scanning the two diagonals and checking each value for primality using a square-root divisibility test. Only 2n elements are examined, making the traversal O(n). The overall complexity becomes O(n * sqrt(m)), where m is the maximum diagonal value.

Q: Is Prime In Diagonal asked at Google/Amazon/Meta?

Problems involving matrix traversal and prime checking appear frequently in coding interviews at companies like Amazon and Google. While this exact problem may vary, the underlying concepts—diagonal iteration, efficient prime testing, and basic number theory—are common interview topics.

Q: What data structure is used in Prime In Diagonal?

The core data structure is a 2D matrix (array). The algorithm simply iterates through indices to access diagonal elements. If using the optimized approach, an additional boolean array is used to store prime flags from the sieve.

Q: What is the time complexity of Prime In Diagonal?

The typical solution runs in O(n * sqrt(m)) time. You check up to 2n diagonal elements and test each number for primality using trial division up to its square root. Space complexity remains O(1) since only a few variables are used.

The 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.

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 == nums_i.length
1 <= nums[i][j] <= 4*10⁶

Approach overview

Problem Overview: You are given an n x n matrix. The task is to scan both the main diagonal (nums[i][i]) and the anti-diagonal (nums[i][n-1-i]) and return the largest value that is a prime number. If neither diagonal contains a prime, return 0. The problem combines simple matrix traversal with efficient prime checking.

Approach 1: Extract and Check Diagonals for Primes (O(n * sqrt(m)) time, O(1) space)

Traverse the matrix once and only inspect the diagonal elements instead of the entire grid. For each index i, evaluate both nums[i][i] (main diagonal) and nums[i][n-1-i] (secondary diagonal). For each value, run a primality test by checking divisibility from 2 up to sqrt(value). Track the maximum prime encountered during the scan. Since only 2n numbers are checked, the traversal cost is linear in n, while the dominant cost comes from the prime check. This approach uses constant extra memory and works well when values are moderately sized. The traversal pattern directly leverages properties of a matrix, while the primality check relies on basic number theory techniques.

Approach 2: Optimized Sieving for Prime Checking (O(M log log M + n) time, O(M) space)

If matrix values can be large and repeated prime checks become expensive, precompute primes using the Sieve of Eratosthenes. First determine the maximum value present on either diagonal. Build a boolean sieve array up to that value to mark prime numbers in O(M log log M) time. Then iterate through the diagonals and simply check sieve[value] in constant time. This replaces repeated square-root primality checks with a fast lookup. The tradeoff is additional memory proportional to the largest number encountered. This method is useful in Python or other interpreted languages where repeated divisor checks may slow down execution. The diagonal iteration itself still uses a simple loop over indices in the array.

Recommended for interviews: The diagonal extraction with square-root prime checking is usually what interviewers expect. It demonstrates that you recognize only 2n elements matter and that you understand basic prime validation. Implementing a sieve is a good optimization discussion point when constraints on element values are large or repeated checks become costly.

Approach 1: Extract and Check Diagonals for Primes

This approach involves directly iterating over each diagonal (main and anti-diagonal) of the 2D array, extracting the elements, checking their primality, and recording the largest prime value.

Python

def is_prime(num):
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True


def largest_prime_in_diagonals(nums):
    max_prime = 0
    n = len(nums)
    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 - i - 1]):
            max_prime = max(max_prime, nums[i][n - i - 1])
    return max_prime


nums = [[1, 2, 3], [5, 17, 7], [9, 11, 10]]
print(largest_prime_in_diagonals(nums))

Java

public class Main {
    public static boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }
        return true;
    }

    public static int largestPrimeInDiagonals(int[][] nums) {
        int maxPrime = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (isPrime(nums[i][i]))
                maxPrime = Math.max(maxPrime, nums[i][i]);
            if (isPrime(nums[i][n - i - 1]))
                maxPrime = Math.max(maxPrime, nums[i][n - i - 1]);
        }
        return maxPrime;
    }

    public static void main(String[] args) {
        int[][] nums = { { 1, 2, 3 }, { 5, 17, 7 }, { 9, 11, 10 } };
        System.out.println(largestPrimeInDiagonals(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

int largestPrimeInDiagonals(const vector<vector<int>>& nums) {
    int maxPrime = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        if (isPrime(nums[i][i]))
            maxPrime = max(maxPrime, nums[i][i]);
        if (isPrime(nums[i][n - i - 1]))
            maxPrime = max(maxPrime, nums[i][n - i - 1]);
    }
    return maxPrime;
}

int main() {
    vector<vector<int>> nums = {{1, 2, 3}, {5, 17, 7}, {9, 11, 10}};
    cout << largestPrimeInDiagonals(nums) << endl;
    return 0;
}

JavaScript

function isPrime(num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 === 0 || num % 3 === 0) return false;
    for (let i = 5; i * i <= num; i += 6) {
        if (num % i === 0 || num % (i + 2) === 0) return false;
    }
    return true;
}

function largestPrimeInDiagonals(nums) {
    let maxPrime = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (isPrime(nums[i][i]))
            maxPrime = Math.max(maxPrime, nums[i][i]);
        if (isPrime(nums[i][n - i - 1]))
            maxPrime = Math.max(maxPrime, nums[i][n - i - 1]);
    }
    return maxPrime;
}

const nums = [[1, 2, 3], [5, 17, 7], [9, 11, 10]];
console.log(largestPrimeInDiagonals(nums));

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    return true;
}

int largestPrimeInDiagonals(int nums[][300], int n) {
    int maxPrime = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime(nums[i][i]) && nums[i][i] > maxPrime)
            maxPrime = nums[i][i];
        if (isPrime(nums[i][n - i - 1]) && nums[i][n - i - 1] > maxPrime)
            maxPrime = nums[i][n - i - 1];
    }
    return maxPrime;
}

int main() {
    int nums[3][300] = {{1, 2, 3}, {5, 6, 7}, {9, 10, 11}};
    int n = 3;
    printf("%d\n", largestPrimeInDiagonals(nums, n));
    return 0;
}

using System;

class Program
{
    static bool IsPrime(int num)
    {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        for (int i = 5; i * i <= num; i += 6)
        {
            if (num % i == 0 || num % (i + 2) == 0)
                return false;
        }
        return true;
    }

    static int LargestPrimeInDiagonals(int[,] nums)
    {
        int maxPrime = 0;
        int n = nums.GetLength(0);
        for (int i = 0; i < n; i++)
        {
            if (IsPrime(nums[i, i]))
                maxPrime = Math.Max(maxPrime, nums[i, i]);
            if (IsPrime(nums[i, n - i - 1]))
                maxPrime = Math.Max(maxPrime, nums[i, n - i - 1]);
        }
        return maxPrime;
    }

    static void Main()
    {
        int[,] nums = {{1, 2, 3}, {5, 17, 7}, {9, 11, 10}};
        Console.WriteLine(LargestPrimeInDiagonals(nums));
    }
}

The Python solution leverages a helper function is_prime to perform primality checks. We extract numbers from the main and anti-diagonals of the nums matrix, and check their primality, storing the largest prime found.

Complexity

Time Complexity: O(n√(max_val)), attributed to checking primality for each diagonal element.
Space Complexity: O(1) given that no additional data structures are required.

Try this approach in the editor

Approach 2: Optimized Sieving for Prime Checking

This approach enhances efficiency by preferring a sieve-based method to check primes once and utilize this lookup for further diagonal checks. This is especially effective when operating over many numbers from which presence of primes needs consistent verification.

Python

def sieve_of_eratosthenes(max_num):
    is_prime = [True] * (max_num + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= max_num:
        if is_prime[p]:
            for i in range(p * p, max_num + 1, p):
                is_prime[i] = False
        p += 1
    return is_prime


def largest_prime_in_diagonals(nums):
    n = len(nums)
    max_num = 4 * 10**6  # Given constraint
    is_prime = sieve_of_eratosthenes(max_num)
    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 - i - 1]]:
            max_prime = max(max_prime, nums[i][n - i - 1])
    return max_prime


nums = [[1, 2, 3], [5, 17, 7], [9, 11, 10]]
print(largest_prime_in_diagonals(nums))

This implementation utilizes a sieve_of_eratosthenes function to pre-compute prime status for all integers up to the largest possible value in nums. With this pre-computation, the diagonal iteration in largest_prime_in_diagonals checks the precomputed list for primality, which drastically reduces redundant calculations.

Complexity

Time Complexity: O(n^2) for the sieve, which provides fast O(1) prime checks for values, and O(n) for diagonal iteration.
Space Complexity: O(max_val) to store the primality array for all numbers up to the largest constraint.

Try this approach in the editor

Approach 3: Math + Simulation

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

Then we iterate the array and check whether the numbers on the diagonals are prime. If so, we update the answer.

The time complexity is O(n times \sqrt{M}), where n and M are the number of rows of the array and the maximum value in the array, respectively. The space complexity is O(1).

TypeScript

function diagonalPrime(nums: number[][]): number {
    const n = nums.length;
    let ans = 0;
    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: number): boolean {
    if (x < 2) {
        return false;
    }
    for (let i = 2; i <= Math.floor(x / i); ++i) {
        if (x % i === 0) {
            return false;
        }
    }
    return true;
}

func diagonalPrime(nums [][]int) (ans int) {
	n := len(nums)
	for i, row := range nums {
		if isPrime(row[i]) {
			ans = max(ans, row[i])
		}
		if isPrime(row[n-i-1]) {
			ans = max(ans, row[n-i-1])
		}
	}
	return
}

func isPrime(x int) bool {
	if x < 2 {
		return false
	}
	for i := 2; i <= x/i; i++ {
		if x%i == 0 {
			return false
		}
	}
	return true
}

Rust

impl Solution {
    pub fn diagonal_prime(nums: Vec<Vec<i32>>) -> i32 {
        let mut ans = 0;
        let n = nums.len();

        for (i, row) in nums.iter().enumerate() {
            if Self::is_prime(row[i]) && row[i] > ans {
                ans = row[i];
            }
            if Self::is_prime(row[n - i - 1]) && row[n - i - 1] > ans {
                ans = row[n - i - 1];
            }
        }

        ans
    }

    fn is_prime(n: i32) -> bool {
        if n < 2 {
            return false;
        }

        let upper = (n as f64).sqrt() as i32;
        for i in 2..=upper {
            if n % i == 0 {
                return false;
            }
        }

        true
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Extract and Check Diagonals for Primes	Time Complexity: O(n√(max_val)), attributed to checking primality for each diagonal element. Space Complexity: O(1) given that no additional data structures are required.
Optimized Sieving for Prime Checking	Time Complexity: O(n^2) for the sieve, which provides fast O(1) prime checks for values, and O(n) for diagonal iteration. Space Complexity: O(max_val) to store the primality array for all numbers up to the largest constraint.
Math + Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Extract and Check Diagonals for Primes	O(n * sqrt(m))	O(1)	General case. Simple implementation and optimal for most constraints.
Optimized Sieving for Prime Checking	O(M log log M + n)	O(M)	When diagonal values are large or many prime checks are required.

Frequently asked questions

Is Prime In Diagonal easy or hard?

Prime In Diagonal is categorized as an Easy problem on LeetCode. The logic involves straightforward diagonal traversal and basic prime checking. The challenge mainly lies in implementing an efficient primality test and recognizing that only diagonal elements matter.

Prime In Diagonal Python/Java solution

Python and Java implementations typically iterate from i = 0 to n-1 and check nums[i][i] and nums[i][n-1-i]. A helper function determines if a number is prime using a square-root loop. The largest prime encountered during the scan is returned.

How to solve Prime In Diagonal in O(n)?

Achieving near O(n) after preprocessing is possible by using the Sieve of Eratosthenes. Precompute primes up to the maximum diagonal value in O(M log log M). After that, checking whether each diagonal element is prime becomes O(1), so the scan of the matrix diagonals takes O(n).

What is the best approach for Prime In Diagonal?

The most practical approach is scanning the two diagonals and checking each value for primality using a square-root divisibility test. Only 2n elements are examined, making the traversal O(n). The overall complexity becomes O(n * sqrt(m)), where m is the maximum diagonal value.

Is Prime In Diagonal asked at Google/Amazon/Meta?

Problems involving matrix traversal and prime checking appear frequently in coding interviews at companies like Amazon and Google. While this exact problem may vary, the underlying concepts—diagonal iteration, efficient prime testing, and basic number theory—are common interview topics.

What data structure is used in Prime In Diagonal?

The core data structure is a 2D matrix (array). The algorithm simply iterates through indices to access diagonal elements. If using the optimized approach, an additional boolean array is used to store prime flags from the sieve.

What is the time complexity of Prime In Diagonal?

The typical solution runs in O(n * sqrt(m)) time. You check up to 2n diagonal elements and test each number for primality using trial division up to its square root. Space complexity remains O(1) since only a few variables are used.

Prime In Diagonal solution and explanation

The problem

Approach overview

Approach 1: Extract and Check Diagonals for Primes

Approach 2: Optimized Sieving for Prime Checking

Approach 3: Math + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Prime In Diagonal solution and explanation

The problem

Approach overview

Approach 1: Extract and Check Diagonals for Primes

Approach 2: Optimized Sieving for Prime Checking

Approach 3: Math + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems