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:
1 and has no positive integer divisors other than 1 and itself.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 <= 300nums.length == numsi.length1 <= nums[i][j] <= 4*106Problem 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.
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.
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.
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.
Python
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.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Extract and Check Diagonals for Primes | Time Complexity: O(n√(max_val)), due to prime checking for elements on the diagonals. |
| 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. |
| Math + Simulation | — |
| 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. |
6361. Prime In Diagonal || Weekly Contest 340 || Leetcode Solutions #subscribe • CodeCake • 1,104 views views
Watch 9 more video solutions →Practice Prime In Diagonal with our built-in code editor and test cases.
Practice on FleetCode