Prime In Diagonal

Easy
900.

Prime In Diagonal

Prime In Diagonal is an easy coding problem on arrays, math and matrix, asked in Amazon, Adobe and Infosys interviews.

Return the largest prime that lies on either diagonal of the square matrix nums, or 0 if neither diagonal holds a prime.

The diagonals are the cells with i == j and the cells with i + j == n - 1.

Example 1

Input
nums = [[1,2,3],[5,6,7],[9,10,11]]
Output
11
Explanation
The diagonals hold 1, 6, 11, 3, 6, 9; the largest prime is 11.

Example 2

Input
nums = [[1,2,3],[5,17,7],[9,11,10]]
Output
17

Example 3

Input
nums = [[1,4],[6,8]]
Output
0
Explanation
No diagonal entry is prime.

Constraints

  • 1 <= nums.length <= 300
  • nums.length == nums[i].length
  • 1 <= nums[i][j] <= 4000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} nums
 * @return {number}
 */
var diagonalPrime = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Prime In Diagonal — Solution in Python, Java & C++

Prime In Diagonal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and math.

Prime In Diagonal is an easy coding problem on arrays, math and matrix, asked in Amazon, Adobe and Infosys interviews.

Problem statement

Return the largest prime that lies on either diagonal of the square matrix nums, or 0 if neither diagonal holds a prime.

The diagonals are the cells with i == j and the cells with i + j == n - 1.

Example 1

Input: nums = [[1,2,3],[5,6,7],[9,10,11]]
Output: 11
Explanation: The diagonals hold 1, 6, 11, 3, 6, 9; the largest prime is 11.

Example 2

Input: nums = [[1,2,3],[5,17,7],[9,11,10]]
Output: 17

Example 3

Input: nums = [[1,4],[6,8]]
Output: 0
Explanation: No diagonal entry is prime.

Constraints

  • 1 <= nums.length <= 300
  • nums.length == nums[i].length
  • 1 <= nums[i][j] <= 4000000

Hints for Prime In Diagonal

  1. Hint 1

    Only 2n cells matter — the two diagonals.

  2. Hint 2

    Test primality by trial division up to the square root.

  3. Hint 3

    Skip the primality test entirely when the value cannot beat the current best.

How to solve Prime In Diagonal

Visit the 2n diagonal cells and keep the largest prime. Checking value > best before testing primality keeps the expensive part rare.

Approach

  1. For each row i, look at nums[i][i] and nums[i][n-1-i].
  2. If a value exceeds the current best, test it for primality by trial division up to its square root.
  3. Return the best found, or 0.

Why it works

Trial division to sqrt(x) is enough because a composite x must have a factor at or below its square root. Writing the loop bound as d * d <= x avoids a floating-point square root entirely, which matters where the harness has no math library. The > best guard means most cells cost one comparison.

Complexity

  • Time — O(n · sqrt(V))
  • Space — O(1)

Pitfalls

  • The two diagonals overlap at the centre of an odd-sized matrix — harmless here, since taking a maximum is idempotent.
  • 1 is not prime, and the answer for 'no prime found' is 0.
  • A sieve up to 4,000,000 also works but is far more memory than the 2n cells need.

Reference solution

Python

from typing import List

def diagonalPrime(nums: List[List[int]]) -> int:
    def is_prime(x: int) -> bool:
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True

    n = len(nums)
    best = 0
    for i in range(n):
        for v in (nums[i][i], nums[i][n - 1 - i]):
            if v > best and is_prime(v):
                best = v
    return best

Java

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

public static int diagonalPrime(int[][] nums) {
    int n = nums.length;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int a = nums[i][i], b = nums[i][n - 1 - i];
        if (a > best && isPrimeDiag(a)) best = a;
        if (b > best && isPrimeDiag(b)) best = b;
    }
    return best;
}

C++

static bool isPrimeDiag(int x) {
    if (x < 2) return false;
    for (int d = 2; (long long) d * d <= x; d++) if (x % d == 0) return false;
    return true;
}

int diagonalPrime(vector<vector<int>>& nums) {
    int n = (int) nums.size();
    int best = 0;
    for (int i = 0; i < n; i++) {
        int a = nums[i][i], b = nums[i][n - 1 - i];
        if (a > best && isPrimeDiag(a)) best = a;
        if (b > best && isPrimeDiag(b)) best = b;
    }
    return best;
}

JavaScript

var diagonalPrime = function(nums) {
    var isPrime = function(x) {
        if (x < 2) return false;
        for (var d = 2; d * d <= x; d++) if (x % d === 0) return false;
        return true;
    };
    var n = nums.length;
    var best = 0;
    for (var i = 0; i < n; i++) {
        var a = nums[i][i], b = nums[i][n - 1 - i];
        if (a > best && isPrime(a)) best = a;
        if (b > best && isPrime(b)) best = b;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal