algoadvance

You are given a 2D integer array nums. Return the largest prime number found in any of the diagonals of the array. If there is no prime number in any of the diagonals, return -1.

A prime number is a positive integer greater than 1 that is divisible only by 1 and itself.

A diagonal is a set of cells where the absolute difference between the row and column indices of any two cells in the set is the same.

For example:

Clarifying Questions

  1. Input Constraints:
    • What is the size range of the 2D array nums?
    • Are all elements in nums guaranteed to be integers?
  2. Output Specifics:
    • Should we assume that if multiple prime numbers exist in different diagonals, we return the largest one?
    • How should we handle multiple diagonals of the same size? For example, in a non-square array.
  3. Edge Cases:
    • Is there a possibility of negative or zero values in nums?
    • Do we need to handle very large arrays where performance considerations are important?

Strategy

  1. Helper Function:
    • Create a helper function is_prime to determine if a given number is prime. Since we may need to check several numbers, this function should be efficient.
  2. Traverse Diagonals:
    • Extract all diagonals from the array nums. This can be done by noting that for a matrix of size m x n, the diagonals can be identified by the fixed differences in row and column indices.
    • We need to consider both the primary diagonals and the secondary diagonals (reversed).
  3. Finding the Largest Prime:
    • Use the is_prime helper function to check each element in the diagonals.
    • Keep track of the largest prime found.

Code

def is_prime(num):
    """Helper function to check if a number is prime."""
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

def largest_prime_in_diagonals(nums):
    """Returns the largest prime number in any diagonal of the array."""
    if not nums or not nums[0]:
        return -1
    
    largest_prime = -1
    rows, cols = len(nums), len(nums[0])
    
    # Check primary diagonals
    for d in range(-(rows - 1), cols):
        diagonal = [nums[i][i - d] for i in range(max(0, d), min(rows, cols + d)) if 0 <= i < rows and 0 <= (i - d) < cols]
        for num in diagonal:
            if is_prime(num) and num > largest_prime:
                largest_prime = num
    
    # Check secondary diagonals
    for d in range(rows + cols - 1):
        diagonal = [nums[i][d - i] for i in range(max(0, d-cols+1), min(rows, d+1)) if 0 <= i < rows and 0 <= (d - i) < cols]
        for num in diagonal:
            if is_prime(num) and num > largest_prime:
                largest_prime = num
    
    return largest_prime

# Example usage:
nums = [
  [1, 2, 3],
  [5, 6, 7],
  [9, 10, 11]
]
print(largest_prime_in_diagonals(nums))  # Output might be 7, assuming it is the largest prime number in the diagonals.

Time Complexity

This solution is efficient for reasonably sized arrays and leverages both diagonal extraction and prime checking effectively.

Try our interview co-pilot at AlgoAdvance.com