algoadvance

Leetcode 2614. Prime In Diagonal

Problem Statement

2614. Prime In Diagonal

You are given a 2D matrix grid of size n x n. Return the largest prime number that lies on either of the two diagonals of grid. In case, no prime number is present on the diagonals, return 0.

A prime number is a natural number greater than 1 which is only divisible by 1 and itself.

A number x is said to be on a diagonal if there exists some index i for which any of the following is true:

Clarifying Questions

  1. Will the matrix always be a square matrix (i.e., n x n)?
    • Yes, the problem explicitly states that the grid is of size n x n.
  2. What is the range of numbers in the matrix?
    • Any feasible range for the problem; typically within integer limits for general problems like this.
  3. What is the value of n? Is it controlled within a specific range?
    • The value of n can vary but is typically manageable within the constraints of computational limits for interviews, say, from 1 to 1000.

Strategy

  1. Identify diagonal elements:
    • From top-left to bottom-right: elements grid[i][i] for i in 0 to n-1.
    • From top-right to bottom-left: elements grid[i][n-i-1] for i in 0 to n-1.
  2. Check for prime numbers:
    • Implement a helper function isPrime(int num) to determine if a number is prime.
  3. Find the largest prime:
    • Iterate through the identified diagonal elements and keep track of the largest prime.
  4. Edge cases:
    • Single-element matrices.
    • Edge matrices with 0 or no primes on the diagonals.

Code

#include <vector>
#include <cmath>
#include <algorithm> // for max function

bool isPrime(int num) {
    // Any number less than 2 is not a prime number
    if (num < 2) return false;
    // Check for factors from 2 up to the square root of num
    for (int i = 2; i <= std::sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

int largestPrimeInDiagonals(const std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int largest_prime = 0;

    for (int i = 0; i < n; ++i) {
        int top_left_diag = grid[i][i];
        int top_right_diag = grid[i][n - i - 1];

        if (isPrime(top_left_diag)) {
            largest_prime = std::max(largest_prime, top_left_diag);
        }
        if (isPrime(top_right_diag)) {
            largest_prime = std::max(largest_prime, top_right_diag);
        }
    }

    return largest_prime;
}

Time Complexity

Thus, the approach remains efficient within the typical constraints of interview problems and ensures we quickly determine the largest prime present on the diagonals.

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