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*106In #2614 Prime In Diagonal, you are given an n x n matrix and must find the largest prime number that appears on either the primary diagonal (i == j) or the secondary diagonal (i + j == n - 1). If no prime exists, return 0.
A simple approach is to iterate through the matrix indices and only inspect the two diagonal elements in each row: nums[i][i] and nums[i][n-1-i]. For each candidate value, perform a prime check. A number is prime if it is greater than 1 and has no divisors up to its square root. Track the maximum prime found while scanning both diagonals.
This method avoids scanning the entire matrix and focuses only on relevant cells. The diagonal traversal takes O(n) steps, while each primality check takes up to O(sqrt(k)) time where k is the value being checked. The algorithm uses constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Scan Primary and Secondary Diagonals with Prime Check | O(n * sqrt(k)) | O(1) |
ThePrimeTime
Use these hints if you're stuck. Try solving on your own first.
Iterate over the diagonals of the matrix and check for each element.
Check if the element is prime or not in O(sqrt(n)) time.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like Prime In Diagonal are common in coding interviews because they test basic matrix traversal and number theory concepts. While the exact question may vary, similar easy-to-medium problems often appear in technical screening rounds.
No special data structure is required for this problem. A simple matrix traversal with integer variables to track the maximum prime is sufficient, making the implementation straightforward and memory efficient.
The optimal approach is to scan only the primary and secondary diagonals of the matrix. For each diagonal value, perform a primality check and track the maximum prime found. This avoids scanning unnecessary cells and keeps the solution efficient.
A number can be checked for primality by testing divisibility from 2 up to the square root of the number. If no divisor is found within this range and the number is greater than 1, it is considered prime.