Scale Engineer

Prime In Diagonal

Easy
#2394Time: 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.1 company
Patterns
MathNumber Theory
Data structures
ArrayMatrix
Companies
IBM

Prompt

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

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 maxPrime to 0.
  • Get the size of the matrix, n = nums.length.
  • Iterate from i = 0 to n-1.
  • Inside the loop, consider the number on the main diagonal: val1 = nums[i][i].
  • Check if val1 is prime using a brute-force helper function isPrime(val1).
  • If isPrime(val1) is true and val1 > maxPrime, update maxPrime = val1.
  • Consider the number on the anti-diagonal: val2 = nums[i][n-1-i].
  • Check if val2 is prime using isPrime(val2).
  • If isPrime(val2) is true and val2 > maxPrime, update maxPrime = val2.
  • After the loop finishes, return maxPrime.

isPrime(num) (Brute-Force):

  1. If num <= 1, return false.
  2. Iterate from j = 2 to num - 1.
  3. If num % j == 0, then num is not prime, return false.
  4. If the loop completes, num is prime, return true.

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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem