Prime In Diagonal

Easy

Asked by:

10 views

Topics:

Arrays

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⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the input matrix, and what is the range of values within the matrix?
Is the input matrix guaranteed to be a square matrix?
If no prime number exists on either diagonal, what should I return?
By 'diagonal', are we referring to only the primary diagonal (top-left to bottom-right) and the secondary diagonal (top-right to bottom-left), or other diagonals as well?
Should I prioritize finding the largest or smallest prime if multiple primes exist on the diagonals?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every number along the diagonals of a grid to see if it's a prime number. We will examine each relevant number one by one, testing its primality.

Here's how the algorithm would work step-by-step:

Start by looking at the numbers that form the main diagonal, which runs from the top left to the bottom right of the grid.
For each of these numbers, check if it's a prime number. To do this, try dividing it by every number from 2 up to the number itself, minus one.
If any of those divisions result in a whole number, then the number is not prime.
If none of those divisions result in a whole number, then the number is prime, and we should remember the largest prime number we've found so far.
Next, look at the numbers that form the other diagonal, which runs from the top right to the bottom left of the grid.
Again, for each of these numbers, check if it's a prime number by trying to divide it by every number from 2 up to the number itself, minus one.
As before, if any division results in a whole number, it's not prime.
If it is prime, compare it to the largest prime we found before, and update our record if the new prime is bigger.
After checking all the numbers on both diagonals, the largest prime number we found is the answer.

Code Implementation

def prime_in_diagonal_brute_force(matrix):
    largest_prime = 0

    matrix_size = len(matrix)

    # Check main diagonal
    for index in range(matrix_size):
        number_to_check = matrix[index][index]

        if number_to_check > 1:
            is_prime = True
            # Primality test
            for divisor in range(2, number_to_check):
                if number_to_check % divisor == 0:
                    is_prime = False
                    break

            # Update largest prime if needed
            if is_prime:
                if number_to_check > largest_prime:
                    largest_prime = number_to_check

    # Check other diagonal
    for index in range(matrix_size):
        number_to_check = matrix[index][matrix_size - 1 - index]

        # We want to only check numbers > 1
        if number_to_check > 1:
            is_prime = True
            # Primality test
            for divisor in range(2, number_to_check):
                if number_to_check % divisor == 0:
                    is_prime = False
                    break

            # Update largest prime if needed
            if is_prime:
                # Update the largest prime
                if number_to_check > largest_prime:
                    largest_prime = number_to_check

    return largest_prime

Big(O) Analysis

Time Complexity

O(n*sqrt(n)) – The algorithm iterates through the main and secondary diagonals of an n x n matrix, which takes O(n) time. For each element on the diagonals, a primality test is performed. The primality test involves iterating from 2 up to the square root of the number being tested. Since the numbers on the diagonals can be as large as the matrix elements, the primality test takes O(sqrt(n)) time in the worst case. Therefore, the overall time complexity is O(n*sqrt(n)).

Space Complexity

O(1) – The provided algorithm checks the primality of numbers along the diagonals. The only extra memory used is for storing the largest prime found so far. This variable, and any temporary variables within the primality test itself (e.g., loop counters), consume a constant amount of space regardless of the grid's dimensions (N, where N represents the number of rows/columns in the grid). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find prime numbers within the diagonals of a grid, we only need to check the numbers present on those diagonals. We'll focus on extracting these diagonal numbers and efficiently testing each one for primality.

Here's how the algorithm would work step-by-step:

First, identify the numbers that lie along the main diagonal (from top-left to bottom-right).
Next, identify the numbers that lie along the anti-diagonal (from top-right to bottom-left).
Combine these two sets of numbers, but be careful not to count the center number twice if the grid has an odd size.
For each number, check if it's greater than 1 because 1 is not a prime.
If the number is greater than 1, determine if it's a prime number by checking if it's divisible by any number from 2 up to its square root. If it is divisible, then it is not a prime and we can stop checking.
Remember the biggest prime number you find as you go through the diagonals.
Return the biggest prime number among the diagonal elements, or 0 if no prime number is found.

Code Implementation

def prime_in_diagonal(matrix):
    maximum_prime = 0
    number_of_rows = len(matrix)

    for i in range(number_of_rows):
        # Check numbers on the main diagonal
        main_diagonal_element = matrix[i][i]
        if main_diagonal_element > 1:
            if is_prime(main_diagonal_element):
                maximum_prime = max(maximum_prime, main_diagonal_element)

        # Check numbers on the anti-diagonal
        anti_diagonal_element = matrix[i][number_of_rows - 1 - i]

        # Prevent double-counting the center element
        if anti_diagonal_element > 1 and i != number_of_rows - 1 - i:
            if is_prime(anti_diagonal_element):
                maximum_prime = max(maximum_prime, anti_diagonal_element)

    return maximum_prime

def is_prime(number):
    # Numbers less than 2 cannot be prime
    if number < 2:
        return False

    # Only need to check divisibility up to the square root
    for i in range(2, int(number**0.5) + 1):
        if number % i == 0:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n * sqrt(n)) – The algorithm iterates through at most 2*n diagonal elements to identify potential prime numbers, where n is the number of rows (or columns) in the grid. For each of these diagonal elements, a primality test is performed. The primality test involves checking divisibility from 2 up to the square root of the element. Therefore, the time complexity of the primality test is proportional to the square root of the element. In the worst case, the elements are of magnitude n, so the primality test takes O(sqrt(n)) time. Thus, the overall time complexity is O(n * sqrt(n)).

Space Complexity

O(1) – The algorithm primarily uses a few scalar variables such as the largest prime found so far and loop counters. It does not create any auxiliary data structures like lists, arrays, or hash maps that scale with the input matrix size N (where N is the number of rows or columns). Thus, the extra space used remains constant, irrespective of the input size.

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately since no diagonal elements exist.
Non-square matrix	Only process the minimum of rows and columns to avoid index out of bounds exceptions.
Matrix with only one element	Check if the single element is prime and return it or 0 if not prime.
Matrix with negative numbers	Prime numbers are greater than 1, so ignore any negative numbers encountered.
Matrix containing zero	Zero is not a prime number, so it should be ignored.
Large numbers in the matrix (potential overflow)	Use appropriate data types (e.g., long) to prevent integer overflow when checking for primality.
All numbers in the matrix are non-prime	Return 0, as no prime numbers were found on the diagonals.
Numbers on both diagonals are the same, and prime.	Return the duplicate prime number without error.

Null or empty matrix

How to Handle:

Return 0 immediately since no diagonal elements exist.

Non-square matrix

How to Handle:

Only process the minimum of rows and columns to avoid index out of bounds exceptions.

Matrix with only one element

How to Handle:

Check if the single element is prime and return it or 0 if not prime.

Matrix with negative numbers

How to Handle:

Prime numbers are greater than 1, so ignore any negative numbers encountered.

Matrix containing zero

How to Handle:

Zero is not a prime number, so it should be ignored.

Large numbers in the matrix (potential overflow)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow when checking for primality.

All numbers in the matrix are non-prime

How to Handle:

Return 0, as no prime numbers were found on the diagonals.

Numbers on both diagonals are the same, and prime.

How to Handle:

Return the duplicate prime number without error.