algoadvance

Leetcode 2614. Prime In Diagonal

Problem Statement

You are given a 2D integer array nums. You are to return the largest prime number that lies on any of the diagonals in the nums array. If there are no prime numbers present in the diagonals, return 0.

A prime number is an integer greater than 1 that has no divisors other than 1 and itself.

Your solution should consider both the primary and the secondary diagonals:

• The primary diagonal of a 2D array element nums[i][j] is where i == j.
• The secondary diagonal of a 2D array element nums[i][j] is where i + j == len(nums) - 1.

Clarifying Questions

1. Q: Can the 2D array have negative numbers or zeroes? A: The array may contain any integers including negative numbers and zeroes. However, for the purpose of this problem, we only consider positive integers greater than 1 as potential prime candidates.

2. Q: What are the constraints on the size of the 2D array? A: Typically, these constraints will be mentioned explicitly within the problem. For now, let’s assume the size is reasonable for typical interview questions, say up to 100x100 elements.

3. Q: Should the solution address edge cases, such as very small arrays or arrays without any primes? A: Yes, the implementation should handle edge cases appropriately and return 0 if no prime numbers are found.

Code

import java.util.*;

public class PrimeInDiagonals {
    
    public static int largestPrimeInDiagonals(int[][] nums) {
        Set<Integer> diagonalElements = new HashSet<>();
        
        int n = nums.length;
        
        // Collecting primary diagonal elements
        for (int i = 0; i < n; i++) {
            diagonalElements.add(nums[i][i]);
        }
        
        // Collecting secondary diagonal elements
        for (int i = 0; i < n; i++) {
            diagonalElements.add(nums[i][n - 1 - i]);
        }
        
        int largestPrime = 0;
        for (int num : diagonalElements) {
            if (isPrime(num)) {
                largestPrime = Math.max(largestPrime, num);
            }
        }
        
        return largestPrime;
    }
    
    private static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        if (num <= 3) {
            return true;
        }
        if (num % 2 == 0 || num % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
    
    // Main method for quick testing
    public static void main(String[] args) {
        int[][] nums1 = {
            {2, 3, 5},
            {7, 11, 13},
            {17, 19, 23}
        };
        System.out.println(largestPrimeInDiagonals(nums1)); // should output 23
        
        int[][] nums2 = {
            {2, 3},
            {5, 7}
        };
        System.out.println(largestPrimeInDiagonals(nums2)); // should output 7
        
        int[][] nums3 = {
            {4, 6},
            {8, 9}
        };
        System.out.println(largestPrimeInDiagonals(nums3)); // should output 0
    }
}

Strategy

1. Extract Diagonal Elements: Traverse the primary and secondary diagonals to collect all the elements in these diagonals.
2. Check for Primes: For each collected element, verify if the number is prime.
3. Find the Largest Prime: Track the largest prime found during the prime-checking phase.

Time Complexity

• Prime Checking: The isPrime function operates in (O(\sqrt{n})) for a single number.
• Extraction and Prime Checking: Extracting elements from the diagonals requires (O(n)) time for a single diagonal. For two diagonals, this results in (O(2n)) which simplifies to (O(n)).
• Total Complexity: The total time complexity is (O(n \sqrt{m})), where (n) is the number of elements in the diagonals (which is linear to the array size) and (\sqrt{m}) is the complexity for checking prime numbers for each element. (m) is the maximum value in the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?