Watch 10 video solutions for Prime In Diagonal, a easy level problem involving Array, Math, Matrix. This walkthrough by CodeCake has 1,104 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |