Skip to main content
Talentd

Prime In Diagonal - Solution & Explanation

EasyArrayMathMatrixNumber Theory15 min readAsked at: Google
Practice this problem

Problem Statement

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 == numsi.length
  • 1 <= nums[i][j] <= 4*106

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.

In this implementation, we start by defining a helper function isPrime to check the primality of a number. We iterate over the array by extracting elements from both the main diagonal and the anti-diagonal, updating the maximum prime found so far. Finally, we return the maximum prime obtained or 0 if no prime was found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n√(max_val)), due to prime checking for elements on the diagonals.
Space Complexity: O(1), since we use a constant amount of space for auxiliary variables.

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.

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.

Code

Python

Python

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

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Extract and Check Diagonals for Primes

Time Complexity: O(n√(max_val)), due to prime checking for elements on the diagonals.
Space Complexity: O(1), since we use a constant amount of space for auxiliary variables.

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—

Detailed Complexity Analysis

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

Video Solution

6361. Prime In Diagonal || Weekly Contest 340 || Leetcode Solutions #subscribe • CodeCake • 1,104 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Prime In Diagonal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays