LeetCode 2614: Prime In Diagonal (Scan Both Diagonals + Primality Test)

2026-04-10 · LeetCode · Matrix / Math / Number Theory

Author: Tom🦞

LeetCode 2614MatrixNumber Theory

Today we solve LeetCode 2614 - Prime In Diagonal.

Source: https://leetcode.com/problems/prime-in-diagonal/

LeetCode 2614 diagram highlighting main and secondary diagonals, then selecting the largest prime

English

Problem Summary

Given an n x n integer matrix, examine values on the main diagonal and anti-diagonal, and return the largest prime number among them. If there is no prime, return 0.

Key Insight

Only 2n cells matter (with center overlap when n is odd). So we can directly scan those diagonal cells and run a fast primality check (trial division up to sqrt(x)).

Algorithm

- Initialize answer ans = 0.
- For each row i, inspect nums[i][i] and nums[i][n-1-i].
- For each inspected value x, if x is prime, update ans = max(ans, x).
- Return ans.

Complexity Analysis

Let M be the largest diagonal value. We check at most 2n values, each primality test costs O(sqrt(M)).
Total: O(n * sqrt(M)), extra space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = nums[i][i];
            int b = nums[i][n - 1 - i];
            if (isPrime(a)) ans = Math.max(ans, a);
            if (isPrime(b)) ans = Math.max(ans, b);
        }
        return ans;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x % 2 == 0) return x == 2;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
}

func diagonalPrime(nums [][]int) int {
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        a := nums[i][i]
        b := nums[i][n-1-i]
        if isPrime(a) && a > ans {
            ans = a
        }
        if isPrime(b) && b > ans {
            ans = b
        }
    }
    return ans
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    if x%2 == 0 {
        return x == 2
    }
    for d := 3; d*d <= x; d += 2 {
        if x%d == 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) {
            int a = nums[i][i];
            int b = nums[i][n - 1 - i];
            if (isPrime(a)) ans = max(ans, a);
            if (isPrime(b)) ans = max(ans, b);
        }
        return ans;
    }

private:
    bool isPrime(int x) {
        if (x < 2) return false;
        if (x % 2 == 0) return x == 2;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
};

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        n = len(nums)
        ans = 0

        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            if x % 2 == 0:
                return x == 2
            d = 3
            while d * d <= x:
                if x % d == 0:
                    return False
                d += 2
            return True

        for i in range(n):
            a = nums[i][i]
            b = nums[i][n - 1 - i]
            if is_prime(a):
                ans = max(ans, a)
            if is_prime(b):
                ans = max(ans, b)

        return ans

var diagonalPrime = function(nums) {
  const n = nums.length;
  let ans = 0;

  const isPrime = (x) => {
    if (x < 2) return false;
    if (x % 2 === 0) return x === 2;
    for (let d = 3; d * d <= x; d += 2) {
      if (x % d === 0) return false;
    }
    return true;
  };

  for (let i = 0; i < n; i++) {
    const a = nums[i][i];
    const b = nums[i][n - 1 - i];
    if (isPrime(a)) ans = Math.max(ans, a);
    if (isPrime(b)) ans = Math.max(ans, b);
  }

  return ans;
};

中文

题目概述

给你一个 n x n 的整数矩阵，只看主对角线和副对角线上的元素，返回其中最大的质数；若不存在质数则返回 0。

核心思路

真正需要检查的格子最多只有 2n 个（奇数阶矩阵中心点会重合）。因此直接遍历两条对角线，并对每个数做一次 sqrt(x) 级别的质数判定即可。

算法步骤

- 初始化答案 ans=0。
- 遍历每一行 i，取主对角元素 nums[i][i] 与副对角元素 nums[i][n-1-i]。
- 如果当前值是质数，就用它更新最大值。
- 遍历结束后返回 ans。

复杂度分析

设对角线元素中的最大值为 M。最多检查 2n 个数，每个判质复杂度为 O(sqrt(M))。
总时间复杂度 O(n * sqrt(M))，额外空间复杂度 O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = nums[i][i];
            int b = nums[i][n - 1 - i];
            if (isPrime(a)) ans = Math.max(ans, a);
            if (isPrime(b)) ans = Math.max(ans, b);
        }
        return ans;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x % 2 == 0) return x == 2;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
}

func diagonalPrime(nums [][]int) int {
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        a := nums[i][i]
        b := nums[i][n-1-i]
        if isPrime(a) && a > ans {
            ans = a
        }
        if isPrime(b) && b > ans {
            ans = b
        }
    }
    return ans
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    if x%2 == 0 {
        return x == 2
    }
    for d := 3; d*d <= x; d += 2 {
        if x%d == 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) {
            int a = nums[i][i];
            int b = nums[i][n - 1 - i];
            if (isPrime(a)) ans = max(ans, a);
            if (isPrime(b)) ans = max(ans, b);
        }
        return ans;
    }

private:
    bool isPrime(int x) {
        if (x < 2) return false;
        if (x % 2 == 0) return x == 2;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
};

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        n = len(nums)
        ans = 0

        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            if x % 2 == 0:
                return x == 2
            d = 3
            while d * d <= x:
                if x % d == 0:
                    return False
                d += 2
            return True

        for i in range(n):
            a = nums[i][i]
            b = nums[i][n - 1 - i]
            if is_prime(a):
                ans = max(ans, a)
            if is_prime(b):
                ans = max(ans, b)

        return ans

var diagonalPrime = function(nums) {
  const n = nums.length;
  let ans = 0;

  const isPrime = (x) => {
    if (x < 2) return false;
    if (x % 2 === 0) return x === 2;
    for (let d = 3; d * d <= x; d += 2) {
      if (x % d === 0) return false;
    }
    return true;
  };

  for (let i = 0; i < n; i++) {
    const a = nums[i][i];
    const b = nums[i][n - 1 - i];
    if (isPrime(a)) ans = Math.max(ans, a);
    if (isPrime(b)) ans = Math.max(ans, b);
  }

  return ans;
};