We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Prime In Diagonal

Difficulty: Easy

Problem Description

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.

Key Insights

  • An integer is prime if it is greater than 1 and has no positive integer divisors other than 1 and itself.
  • The elements on the primary diagonal can be accessed via nums[i][i].
  • The elements on the secondary diagonal can be accessed via nums[i][nums.length - i - 1].
  • We need to find all unique numbers on both diagonals and check which of these are prime.
  • The goal is to return the largest prime number found, or 0 if no prime exists.

Space and Time Complexity

Time Complexity: O(n) for traversing the diagonals, plus O(sqrt(m)) for checking primality for each diagonal element, where m is the maximum value in the diagonals.

Space Complexity: O(n) for storing diagonal elements in a set to check for uniqueness.

Solution

To solve the problem, we will:

  1. Iterate through the matrix to collect all elements on both the primary and secondary diagonals.
  2. Use a helper function to determine if a number is prime.
  3. Keep track of the largest prime number found during our checks.
  4. Return the largest prime number or 0 if none are found.

We will use a set to ensure uniqueness of diagonal elements and a simple trial division method to check for primality.

Code Solutions

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def largest_prime_in_diagonal(nums):
    n = len(nums)
    primes = set()

    for i in range(n):
        primes.add(nums[i][i])  # Primary diagonal
        primes.add(nums[i][n - i - 1])  # Secondary diagonal

    largest_prime = 0
    for num in primes:
        if is_prime(num):
            largest_prime = max(largest_prime, num)

    return largest_prime
← Back to All Questions