Prime In Diagonal

EASY

Description

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 == nums_i.length
1 <= nums[i][j] <= 4*10⁶

Approaches

Checkout 3 different approaches to solve Prime In Diagonal. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Primality Test

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):

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

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 Analysis

Time Complexity: 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 Complexity: O(1) extra space.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Prime In Diagonal. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Prime In Diagonal

Patterns:

MathNumber Theory

Data Structures:

ArrayMatrix

Companies:

IBM |