2614. Prime In Diagonal

EasyArrayMathMatrixNumber Theory
Leetcode Link

Problem Description

In this problem, we are given a square two-dimensional integer array nums which is 0-indexed. The task is to find the largest prime number that is present on either or both of the two main diagonals of this array.

The first main diagonal runs from the top-left corner to the bottom-right corner and includes elements where the row and column indices are equal, i.e., nums[i][i]. The second main diagonal goes from the top-right corner to the bottom-left corner, consisting of elements nums[i][nums.length - i - 1].

A number is considered prime if it's greater than 1 and does not have any divisors other than 1 and itself. If no prime numbers are found on the diagonals, the function should return 0.

An example illustration provided in the problem statement shows a grid where the first diagonal is [1,5,9] and the second diagonal is [3,5,7].

Intuition

The intuition behind the solution is straightforward. Since the problem requires us to only inspect elements along the diagonals of a square matrix, we don't need to consider every element in the array.

We define a utility function, is_prime, that determines if a given number is prime. The function iterates from 2 to sqrt(x) where x is the number we're testing for primality, and checks if x is divisible by any number in this range. If x is divisible, then it is not a prime number. We use the square root of x as an optimization because a larger factor of x would have a corresponding smaller factor that would have been identified by the time we reach sqrt(x).

The solution approach involves iterating through each row of the array once, inspecting two elements in each row - one from each diagonal. For each of these elements, we use the is_prime function to check if it's prime. If it is, we update our answer with this value if it happens to be greater than the current answer.

This way, by the end of the iteration, we'll have checked all numbers on both diagonals and kept track of the largest prime number encountered. The answer is the maximum prime number found; or 0 if there were no prime numbers on the diagonals.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The algorithm follows the steps outlined in the intuition section. Specifically, we make use of a simple linear scan through the diagonals of the matrix and a prime-checking function.

Here is a step-by-step breakdown of the implementation:

  1. We define a helper function is_prime which takes an integer x as an argument. This function checks if x is a prime number by attempting to find a divisor from 2 to sqrt(x).

    1def is_prime(x: int) -> bool:
    2    if x < 2:
    3        return False
    4    return all(x % i for i in range(2, int(sqrt(x)) + 1))
    • If x is less than 2, it is not prime by definition, and the function returns False.
    • Otherwise, it uses the all function along with a generator expression to check for any divisors. If any divisor is found (the remainder is zero), all will return False, and the function will also return False, indicating that x is not prime.
    • If no divisors are found, the number is prime, and True is returned.
  2. The main diagonalPrime function scans the matrix's diagonals. It initializes ans to 0, which will store the largest prime found.

    1n = len(nums)
    2ans = 0
  3. It then uses a loop to iterate through each element of the array, but only checks the values at the diagonal positions - nums[i][i] and nums[i][n - i - 1]:

    1for i, row in enumerate(nums):
    2    if is_prime(row[i]):
    3        ans = max(ans, row[i])
    4    if is_prime(row[n - i - 1]):
    5        ans = max(ans, row[n - i - 1])
    • In this loop, enumerate(nums) is used to get both the index i and the row of the matrix.
    • We check both elements on the diagonals using our is_prime function.
    • If the number on the diagonal is prime, we update ans with the larger of ans and the prime number found.
    • The use of the max function ensures that we always have the largest prime number encountered.
  4. After the for loop completes, we return ans, which by then contains the largest prime number found on the diagonals or remains at its initial value, 0, if there were no prime numbers.

Returning ans completes the function:

1return ans

No additional data structures are needed for this approach, and the patterns used are direct access of items in an array and linear iteration, which keeps the space complexity to O(1) and time complexity to O(n * sqrt(m)) (where n is the length of a side of the square matrix and m is the value of the largest number to be checked for primality).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the following 3x3 grid for the array nums:

1nums = [
2  [11,  2, 5],
3  [ 9,  7, 4],
4  [ 1,  6, 3]
5]
  1. The first main diagonal elements are nums[0][0], nums[1][1], nums[2][2], which are 11, 7, 3, respectively. The second main diagonal elements are nums[0][2], nums[1][1], nums[2][0], which are 5, 7, 1.

  2. Now, we define our is_prime function and use it to check each number along the diagonals for primality:

    • 11 is prime.
    • 7 is prime (noted twice as it appears in both diagonals).
    • 3 is prime.
    • 5 is prime.
    • 1 is not prime since it is less than 2.
  3. As we iterate through the diagonals, we use the is_prime function and keep track of the largest prime number:

    • When we check nums[0][0], which is 11, it's prime, and since ans is initially 0, we now update ans to 11.
    • Checking nums[0][2] gives us 5, which is prime but less than 11, so ans remains 11.
    • Next, both nums[1][1] and nums[2][0] yield a 7, which is prime, but still less than 11, so ans remains unchanged.
    • Finally, nums[2][2] is 3, also prime, but less than the current ans of 11.
  4. After inspecting all numbers on both diagonals, the largest prime number we found is 11, so our function returns 11. If no prime numbers had been encountered, ans would have remained 0, and the function would return 0.

This example captures all steps in the algorithm, iterates over the diagonals while checking for primality, and concludes by returning the largest prime found or 0. It demonstrates how the is_prime function works in conjunction with the linear iteration over array elements, meeting the objective of the problem with efficiency in terms of time and space complexity.

Solution Implementation

1from typing import List
2from math import isqrt
3
4class Solution:
5    def diagonal_prime(self, nums: List[List[int]]) -> int:
6        # Helper function to check if a number is prime
7        def is_prime(x: int) -> bool:
8            if x < 2:
9                return False  # Numbers less than 2 are not prime
10            for i in range(2, isqrt(x) + 1):  # Iterating only up to the square root of x
11                if x % i == 0:
12                    return False  # Number is divisible by i, hence not prime
13            return True  # Number is prime as it wasn't divisible by any i
14
15        # Get the length of the square matrix
16        n = len(nums)
17        # Initialize the maximum prime number found on the diagonals as 0
18        max_prime = 0
19        # Loop through each row of the matrix
20        for i, row in enumerate(nums):
21            # Check if the element in the primary diagonal is prime
22            if is_prime(row[i]):
23                max_prime = max(max_prime, row[i])
24            # Check if the element in the secondary diagonal is prime
25            if is_prime(row[n - i - 1]):
26                max_prime = max(max_prime, row[n - i - 1])
27        # Return the largest prime number found on the diagonals
28        return max_prime
29
1class Solution {
2    // Method to find the maximum prime number on either of the diagonals of a square matrix
3    public int diagonalPrime(int[][] matrix) {
4        int size = matrix.length; // The length of the matrix (number of rows)
5        int maxPrime = 0; // Variable to store the maximum prime number found
6
7        // Loop through the matrix from the first row to the last row
8        for (int i = 0; i < size; ++i) {
9            // Check if the element on the primary diagonal is prime
10            if (isPrime(matrix[i][i])) {
11                maxPrime = Math.max(maxPrime, matrix[i][i]); // Update max if it's a new maximum
12            }
13            // Check if the element on the secondary diagonal is prime
14            if (isPrime(matrix[i][size - i - 1])) {
15                maxPrime = Math.max(maxPrime, matrix[i][size - i - 1]); // Update max if it's a new maximum
16            }
17        }
18        return maxPrime; // Return the largest prime number found on the diagonals
19    }
20
21    // Helper method to check if an integer is prime
22    private boolean isPrime(int number) {
23        // Numbers less than 2 are not prime
24        if (number < 2) {
25            return false;
26        }
27        // Check for factors from 2 to the square root of number
28        for (int i = 2; i <= number / i; ++i) {
29            // If a divisor is found, number is not prime
30            if (number % i == 0) {
31                return false;
32            }
33        }
34        // No divisors were found; number is prime
35        return true;
36    }
37}
38
1class Solution {
2public:
3    // Function to find the maximum prime number on both diagonals of a square matrix.
4    int diagonalPrime(vector<vector<int>>& matrix) {
5        int size = matrix.size();  // The size of the NxN matrix.
6        int maxPrime = 0;  // Variable to keep track of the maximum prime found.
7
8        // Loop through each element on the diagonals of the matrix.
9        for (int i = 0; i < size; ++i) {
10            // Check the primary diagonal element for primality. 
11            if (isPrime(matrix[i][i])) {
12                maxPrime = max(maxPrime, matrix[i][i]);
13            }
14            // Check the secondary diagonal element for primality. 
15            if (isPrime(matrix[i][size - i - 1])) {
16                maxPrime = max(maxPrime, matrix[i][size - i - 1]);
17            }
18        }
19        return maxPrime;  // Return the maximum prime number found on the diagonals.
20    }
21
22    // Helper function to check if a number is prime.
23    bool isPrime(int num) {
24        if (num < 2) {
25            return false;  // Numbers less than 2 are not prime.
26        }
27        // Check divisibility of num from 2 to sqrt(num).
28        for (int i = 2; i <= num / i; ++i) { 
29            if (num % i == 0) {
30                return false;  // num is divisible by i, hence not prime.
31            }
32        }
33        return true;  // num is prime as it wasn't divisible by any number from 2 to sqrt(num).
34    }
35};
36
1// Function to check if a number is prime.
2const isPrime = (num: number): boolean => {
3  if (num < 2) {
4    return false; // Numbers less than 2 are not prime.
5  }
6  // Check the divisibility of num from 2 to the square root of num.
7  for (let i = 2; i * i <= num; i++) {
8    if (num % i === 0) {
9      return false; // num is divisible by i, hence not prime.
10    }
11  }
12  return true; // num is prime as it wasn't divisible by any number from 2 to sqrt(num).
13};
14
15// Function to find the maximum prime number on both diagonals of a square matrix.
16const diagonalPrime = (matrix: number[][]): number => {
17  const size: number = matrix.length; // The size of the NxN matrix.
18  let maxPrime: number = 0; // Variable to keep track of the maximum prime found.
19
20  // Loop through each element on the diagonals of the matrix.
21  for (let i = 0; i < size; i++) {
22    // Check the primary diagonal element for primality.
23    if (isPrime(matrix[i][i])) {
24      maxPrime = Math.max(maxPrime, matrix[i][i]);
25    }
26    // Check the secondary diagonal element for primality.
27    if (isPrime(matrix[i][size - i - 1])) {
28      maxPrime = Math.max(maxPrime, matrix[i][size - i - 1]);
29    }
30  }
31  return maxPrime; // Return the maximum prime number found on the diagonals.
32};
33
34// Example usage:
35// const myMatrix: number[][] = [[3, 2, 3], [2, 7, 11], [17, 14, 5]];
36// const maxDiagonalPrime: number = diagonalPrime(myMatrix);
37// console.log(maxDiagonalPrime); // Outputs the maximum prime number found on the diagonals.
38
Not Sure What to Study? Take the 2-min Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily influenced by two operations: the iteration over the rows of the matrix and the check for prime numbers.

  1. There is a loop over the n rows of the input matrix nums. For each row, the code checks if the elements at the primary diagonal (row[i]) and the secondary diagonal (row[n - i - 1]) are prime.
  2. The function is_prime is used to determine if a number is prime, which operates in O(sqrt(x)), where x is the number being checked for primality.

Given that the method is_prime is called at most twice for each of the n rows of the matrix, the overall time complexity is O(n * sqrt(M)). Here, M represents the value of the largest number within the matrix, which is being checked for primality.

Thus, the resulting formula for time complexity is: O(n * sqrt(M)).

Space Complexity

The space complexity is determined by the amount of extra memory space required by the algorithm.

  • No extra space is needed apart from a few variables (n, ans, i, and row), which are not dependent on the size of the input.
  • The is_prime function uses a range within a loop, but since Python’s range function generates values on the fly, it does not add to space complexity.

As a result, the space complexity of the algorithm is O(1), indicating constant space usage regardless of input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫