Skip to content

2614. Prime In Diagonal 👍

  • Time: $O(n \cdot \sqrt{\max(\texttt{nums})})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int diagonalPrime(vector<vector<int>>& nums) {
    int ans = 0;
    for (int i = 0; i < nums.size(); ++i) {
      const int a = nums[i][i];
      const int b = nums[i][nums.size() - i - 1];
      if (isPrime(a))
        ans = max(ans, a);
      if (isPrime(b))
        ans = max(ans, b);
    }
    return ans;
  }

 private:
  bool isPrime(int n) {
    if (n <= 1)
      return false;
    for (int i = 2; i * i <= n; ++i)
      if (n % i == 0)
        return false;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int diagonalPrime(int[][] nums) {
    int ans = 0;
    for (int i = 0; i < nums.length; ++i) {
      final int a = nums[i][i];
      final int b = nums[i][nums.length - i - 1];
      if (isPrime(a))
        ans = Math.max(ans, a);
      if (isPrime(b))
        ans = Math.max(ans, b);
    }
    return ans;
  }

  private boolean isPrime(int n) {
    if (n <= 1)
      return false;
    for (int i = 2; i * i <= n; ++i)
      if (n % i == 0)
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def diagonalPrime(self, nums: List[List[int]]) -> int:
    def isPrime(n: int) -> bool:
      if n <= 1:
        return False
      for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
          return False
      return True

    primes1 = [row[i]
               for i, row in enumerate(nums) if isPrime(row[i])]
    primes2 = [row[-i - 1]
               for i, row in enumerate(nums) if isPrime(row[-i - 1])]
    return max(max(primes1) if primes1 else 0,
               max(primes2) if primes2 else 0)