Prime In Diagonal
EasyPrompt
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
1and has no positive integer divisors other than1and itself. - An integer
valis on one of the diagonals ofnumsif there exists an integerifor whichnums[i][i] = valor anifor whichnums[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*106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through the two diagonals of the matrix. For each number encountered, a helper function is called to check if it is a prime number. The largest prime found is tracked and returned. The primality test is done in a naive way by checking for divisibility from 2 up to the number itself minus one.
Algorithm
- Initialize a variable
maxPrimeto 0. - Get the size of the matrix,
n = nums.length. - Iterate from
i = 0ton-1. - Inside the loop, consider the number on the main diagonal:
val1 = nums[i][i]. - Check if
val1is prime using a brute-force helper functionisPrime(val1). - If
isPrime(val1)is true andval1 > maxPrime, updatemaxPrime = val1. - Consider the number on the anti-diagonal:
val2 = nums[i][n-1-i]. - Check if
val2is prime usingisPrime(val2). - If
isPrime(val2)is true andval2 > maxPrime, updatemaxPrime = val2. - After the loop finishes, return
maxPrime.
isPrime(num) (Brute-Force):
- If
num <= 1, returnfalse. - Iterate from
j = 2tonum - 1. - If
num % j == 0, thennumis not prime, returnfalse. - If the loop completes,
numis prime, returntrue.
Walkthrough
The main logic iterates through the rows of the matrix from i = 0 to n-1, where n is the side length of the square matrix. In each iteration, it picks the two diagonal elements: nums[i][i] (main diagonal) and nums[i][n-1-i] (anti-diagonal). A helper function, isPrime(num), is used to determine primality. This function checks for divisibility by every integer from 2 up to num - 1. If a number is found to be prime and is larger than the current maximum prime found, the maximum is updated. The final result is the largest prime number found after checking all diagonal elements.
class Solution { private boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } public int diagonalPrime(int[][] nums) { int n = nums.length; int maxPrime = 0; for (int i = 0; i < n; i++) { // Main diagonal int val1 = nums[i][i]; if (isPrime(val1)) { maxPrime = Math.max(maxPrime, val1); } // Anti-diagonal int val2 = nums[i][n - 1 - i]; if (isPrime(val2)) { maxPrime = Math.max(maxPrime, val2); } } return maxPrime; }}Complexity
Time
O(N * M), where `N` is the side length of the matrix and `M` is the maximum value of an element. For each of the `~2*N` diagonal elements, the primality test takes up to `O(M)` time.
Space
O(1) extra space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to the naive primality test.
Will not pass the time limits for the given constraints, resulting in a 'Time Limit Exceeded' error.
This method improves performance by pre-computing all prime numbers up to the maximum possible value in the input matrix (4*10^6). It uses the Sieve of Eratosthenes algorithm to create a lookup table (a boolean array) indicating whether each number is prime. This allows for constant-time primality checks for the diagonal elements.
Algorithm
- Create a boolean array
isPrimeup to4*10^6 + 1. - Populate the array using the Sieve of Eratosthenes algorithm. This involves marking all numbers as potentially prime, then iterating from 2 and marking all multiples of each prime number as not prime.
- Initialize
maxPrime = 0. - Iterate
ifrom0ton-1. - Check
nums[i][i]: IfisPrime[nums[i][i]]is true, updatemaxPrime = Math.max(maxPrime, nums[i][i]). - Check
nums[i][n-1-i]: IfisPrime[nums[i][n-1-i]]is true, updatemaxPrime = Math.max(maxPrime, nums[i][n-1-i]). - Return
maxPrime.
Walkthrough
First, we determine the upper bound for the numbers, which is M = 4*10^6. We create a boolean array sieve of size M+1. sieve[i] will be true if i is prime, and false otherwise. The Sieve of Eratosthenes algorithm is applied to populate this array. After the sieve is built, we iterate through the diagonals of the nums matrix. For each diagonal number val, we can now check if it's prime in O(1) time by looking up sieve[val]. We keep track of the largest prime found and return it.
import java.util.Arrays; class Solution { private static final int MAX_VAL = 4000001; private static boolean[] isPrime = new boolean[MAX_VAL]; // Static block to pre-compute primes using Sieve static { Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int p = 2; p * p < MAX_VAL; p++) { if (isPrime[p]) { for (int i = p * p; i < MAX_VAL; i += p) { isPrime[i] = false; } } } } public int diagonalPrime(int[][] nums) { int n = nums.length; int maxPrime = 0; for (int i = 0; i < n; i++) { // Main diagonal int val1 = nums[i][i]; if (isPrime[val1]) { maxPrime = Math.max(maxPrime, val1); } // Anti-diagonal int val2 = nums[i][n - 1 - i]; if (isPrime[val2]) { maxPrime = Math.max(maxPrime, val2); } } return maxPrime; }}Complexity
Time
O(M log log M + N), where `M` is the maximum value and `N` is the matrix side length. The sieve creation `O(M log log M)` dominates the runtime. The subsequent traversal of the diagonal is `O(N)`.
Space
O(M), where `M` is the maximum possible value of a number (`4*10^6`). This is required to store the sieve array.
Trade-offs
Pros
Very fast primality checks (
O(1)) after the initial setup.Efficient if many primality tests are needed on numbers within the pre-computed range.
Cons
Uses significant memory (
O(M)) to store the sieve.The one-time cost of building the sieve can be higher than performing individual checks if the number of checks is small.
For the given constraints, this approach is slightly less time-efficient than the optimized trial division method.
This is a significant improvement over the brute-force method and the most efficient approach for the given constraints. It uses an optimized helper function to check for primality. The key optimization is that instead of checking for divisors up to n-1, it only checks up to the square root of n, which is mathematically sufficient.
Algorithm
- Initialize
maxPrime = 0. - Iterate
ifrom0ton-1. - Check
nums[i][i]: If it's a prime (using the optimized method) and greater thanmaxPrime, updatemaxPrime. - Check
nums[i][n-1-i]: If it's a prime and greater thanmaxPrime, updatemaxPrime. - Return
maxPrime.
isPrime(num) (Optimized):
- If
num <= 1, returnfalse. - For
dfrom2tosqrt(num): ifnum % d == 0, returnfalse. - Return
true.
Walkthrough
The overall structure remains the same: iterate through the diagonals and check each number. The key improvement is in the isPrime(num) helper function. A number num is not prime if it has a divisor d such that 1 < d < num. If such a divisor exists, there must be one that is less than or equal to sqrt(num). Therefore, the isPrime function only needs to check for divisibility by integers from 2 up to sqrt(num). This drastically reduces the number of operations for the primality test, making the overall solution very efficient.
class Solution { private boolean isPrime(int n) { if (n <= 1) { return false; } // Check for divisors only up to the square root of n. for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } public int diagonalPrime(int[][] nums) { int n = nums.length; int maxPrime = 0; for (int i = 0; i < n; i++) { // Main diagonal int val1 = nums[i][i]; if (isPrime(val1)) { maxPrime = Math.max(maxPrime, val1); } // Anti-diagonal // Note: if i == n-1-i, we check the same element twice, which is fine. int val2 = nums[i][n - 1 - i]; if (isPrime(val2)) { maxPrime = Math.max(maxPrime, val2); } } return maxPrime; }}Complexity
Time
O(N * sqrt(M)), where `N` is the side length of the matrix and `M` is the maximum value of an element. For each of the `~2*N` diagonal elements, the primality test takes `O(sqrt(M))` time. This is the most time-efficient solution for the given constraints.
Space
O(1) extra space.
Trade-offs
Pros
Excellent balance of time and space efficiency.
Fast enough for the given constraints.
Uses minimal memory (
O(1)).Simpler to implement than the Sieve approach.
Cons
Can be slower than a pre-computation approach if a very large number of primality tests were needed, but for this problem's constraints, it is the most efficient.
Solutions
Solution
class Solution {public int diagonalPrime(int[][] nums) { int n = nums.length; int ans = 0; for (int 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; }private boolean isPrime(int x) { if (x < 2) { return false; } for (int i = 2; i <= x / i; ++i) { if (x % i == 0) { return false; } } return true; }}/** * @param {number[][]} nums * @return {number} */ var diagonalPrime = function ( nums ) { let ans = 0 ; const n = nums . length ; 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 ) { if ( x < 2 ) { return false ; } for ( let i = 2 ; i * i <= x ; i ++ ) { if ( x % i === 0 ) { return false ; } } return true ; }class Solution {public: int diagonalPrime(vector<vector<int>> &nums) { int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) { if (isPrime(nums[i][i])) { ans = max(ans, nums[i][i]); } if (isPrime(nums[i][n - i - 1])) { ans = max(ans, nums[i][n - i - 1]); } } return ans; } bool isPrime(int x) { if (x < 2) { return false; } for (int i = 2; i <= x / i; ++i) { if (x % i == 0) { return false; } } return true; }};class Solution: def diagonalPrime(self, nums: List[List[int]]) -> int: def is_prime(x: int) -> bool: if x < 2: return False return all(x % i for i in range(2, int(sqrt(x)) + 1)) n = len(nums) ans = 0 for i, row in enumerate(nums): if is_prime(row[i]): ans = max(ans, row[i]) if is_prime(row[n - i - 1]): ans = max(ans, row[n - i - 1]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.