Prime In Diagonal
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.
Note that:
1) An integer is prime if it is greater than 1 and has no positive integer divisors other than 1 and itself.
2) 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.
If we look at the constraints given matrix nums is a square matrix.
What is a Square Matrix?
A square matrix is a grid of numbers with an equal number of rows and columns. For example:
Matrix: [[1,2,3],[4,5,6],[7,8,9]]
This is a 3x3 matrix because it has 3 rows and 3 columns.
Square matrices are special because they have two important diagonals:
- Primary Diagonal: This diagonal goes from the top-left corner to the bottom-right corner. For example, in a 3x3 matrix, the elements on the primary diagonal are the ones where the row and column indices are the same (mat[0][0], mat[1][1], mat[2][2]). Elements 1, 5, 9 in the above example are the primary diagonals.
- Secondary Diagonal: This diagonal goes from the top-right corner to the bottom-left corner. For example, in a 3x3 matrix, these elements are at positions where the sum of the row and column indices equals the size of the matrix minus one (mat[0][2], mat[1][1], mat[2][0]). Elements 3, 5, 7 in the above example are the secondary diagonals.
Example
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.
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 == numsi.length
- 1 <= nums[i][j] <= 4*10^6
The initial idea is to traverse the given matrix and check the elements at both diagonals. We are particularly interested in identifying the prime numbers present on these diagonals. The challenge now lies in determining how to efficiently identify and verify prime numbers, as well as how to check for the presence of such primes on the two diagonals. Let’s explore how we can approach this problem.
Optimal Approach
Intuition
To solve this problem, we can simplify our approach by focusing on the diagonals of the matrix and continuously tracking the maximum prime number. First, we identify the two diagonals: the primary diagonal, where the row and column indices are the same (nums[i][i]), and the secondary diagonal, where the sum of the row and column indices equals nums.length - 1 (nums[i][nums.length - i - 1]).
As we loop through these diagonals, we check each number to see if it's prime.
How to check if a number is prime or not?
Understanding Prime Numbers
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This means a number is prime if it cannot be divided evenly by any number other than 1 and itself.
For example:
- 2 is prime because it can only be divided by 1 and 2.
- 3 is prime because it can only be divided by 1 and 3.
- 4 is not prime because it can be divided by 1, 2, and 4.
Now, let’s explore the process of checking whether a number is prime, from a brute-force approach to an optimized method.
Brute Force Approach
The brute-force approach for checking whether a number n is prime involves checking every integer from 2 to n-1 to see if it divides n without a remainder. If we find any such divisor, then n is not prime. Otherwise, it is prime.
Steps:
- Start at 2: We begin by checking if n is divisible by 2 (the smallest prime number).
- Check divisibility: We then check divisibility by every number up to n-1. If any number divides n evenly (i.e., n % i == 0 for any i), then n is not prime.
- Conclude primality: If no such divisor is found, n is prime.
Pseudocode:
function isPrime(n):
if n <= 1: return False
for i = 2 to n-1:
if n % i == 0:
return False
return True
Time Complexity: The brute-force approach has a time complexity of O(n), because in the worst case, we have to check all numbers from 2 to n-1.
Optimized Approach: Checking Up to √n
The brute-force approach can be slow for larger numbers, especially if n is large (e.g., in the order of millions or more). We can optimize the process by realizing that if n is divisible by any number i, then i must be less than or equal to the square root of n. Here's why:
- If n = a * b, then at least one of a or b must be less than or equal to √n. If both a and b were greater than √n, then their product would exceed n, which is not possible.
- Therefore, we don’t need to check every number up to n-1; checking only up to √n is enough to determine if a number is prime.
Steps:
- Initial checks: We check if n is less than 2 (if so, it’s not prime).
- Even number check: If n is greater than 2 and even, we immediately return false, because the only even prime number is 2.
- Odd divisors: We check divisibility from 3 up to √n, but we only check odd numbers. This is because even numbers (other than 2) cannot be prime.
- Conclude primality: If no divisors are found, n is prime.
Pseudocode:
function isPrime(n):
if n <= 1: return False
if n == 2: return True // Special case for 2 (the only even prime)
if n % 2 == 0: return False // If n is even, it's not prime
for i = 3 to sqrt(n) with step 2:
if n % i == 0:
return False
return True
Time Complexity: The time complexity is reduced to O(√n), because we only check divisibility up to the square root of n.
Final Optimized Approach: Sieve of Eratosthenes (Precomputing Primes)
If we need to check for primes multiple times, the Sieve of Eratosthenes is an even more efficient method. Instead of checking if each number is prime individually, we can precompute all primes up to a certain limit, and then simply look up whether a number is prime in constant time.
Steps:
- Create a sieve array: We create an array sieve of size n+1 where sieve[i] will be True if i is prime, and False otherwise.
- Mark non-primes: Starting from 2, mark all multiples of each prime number as non-prime.
- Use the sieve: Once the sieve is built, checking if a number is prime becomes a simple array lookup.
Pseudocode:
function sieveOfEratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False // 0 and 1 are not prime
for i = 2 to sqrt(limit):
if sieve[i] == True:
for j = i * i to limit step i:
sieve[j] = False
return sieve
// To check if a number n is prime:
function isPrime(n, sieve):
return sieve[n]
Time Complexity:
- Building the sieve takes O(n log log n) time.
- Checking if a number is prime takes O(1) time once the sieve is precomputed.
Depending on the use case (whether we need to check primality once or multiple times), we can choose the most efficient method. For individual checks, the √n approach is sufficient, while for multiple checks, the sieve is ideal.
If it is a prime number, we compare it with the current maximum prime we’ve found so far. If the current number is greater than the previously found prime, we update the maximum. This allows us to continuously track the largest prime number on the diagonals without needing to store all the primes.
Finally, after we’ve checked both diagonals, if we have found any prime numbers, we return the largest one. If no prime numbers were found, we return 0.
Approach
Step 1: Precompute All Primes up to the Maximum Value
To efficiently check whether numbers are prime, we will use the Sieve of Eratosthenes. Since the largest value in the matrix can be as large as 4 * 10^6 (from the problem constraints), we will first compute all prime numbers up to 4 * 10^6.
- Initialize the sieve array: Create a boolean array sieve[] of size 4 * 10^6 + 1 (to handle all numbers up to the maximum possible value), where each index will be marked True if the number is prime and False otherwise.
- Mark non-prime numbers: Use the Sieve of Eratosthenes method to mark non-prime numbers in the array. Start by marking all multiples of each prime as non-prime, starting from 2, up to √(4 * 10^6).
- Using the sieve for prime checks: After creating the sieve, checking if a number is prime becomes an O(1) operation, since we can directly access the sieve array.
Step 2: Traverse the Diagonals of the Matrix
After creating the sieve, we will traverse both diagonals of the given matrix. For each element at position i, we will:
- Check the primary diagonal element nums[i][i].
- Check the secondary diagonal element nums[i][n - 1 - i], where n is the size of the matrix.
While doing this, we must ensure that we don’t count the middle element twice when the matrix size is odd, as it belongs to both diagonals.
For each diagonal element, we will use the sieve array to check whether the number is prime. If it is prime, we will track the largest prime encountered so far.
Step 3: Return the Largest Prime
After traversing all the diagonal elements, return the largest prime found.
Dry Run
Input: nums = [[1, 2, 3], [5, 6, 7], [9, 10, 11]]
Initialization:
- maxPrime: Initialized to 0, to store the largest prime number found on the diagonals.
- n: 3 (size of the matrix).
Sieve of Eratosthenes:
Before starting the loop, we precompute all primes up to 4 * 10^6 using the sieve, so we can check if a number is prime in O(1) time.
Loop Iterations:
Iteration 1 (i = 0):
- Primary diagonal element: nums[0][0] = 1
Checking 1 in the sieve reveals it is not prime, so we skip it. - Secondary diagonal element: nums[0][2] = 3
Checking 3 in the sieve shows it is prime.
Update maxPrime = 3.
Iteration 2 (i = 1):
- Primary diagonal element: nums[1][1] = 6
Checking 6 in the sieve shows it is not prime, so we skip it. - Secondary diagonal element: nums[1][1] = 6
This is the same as the primary diagonal element (middle element in an odd-sized matrix). It has already been checked, so we skip it.
Iteration 3 (i = 2):
- Primary diagonal element: nums[2][2] = 11
Checking 11 in the sieve reveals it is prime.
Update maxPrime = 11 (since 11 > 3). - Secondary diagonal element: nums[2][0] = 9
Checking 9 in the sieve shows it is not prime, so we skip it.
Final Output:
- The largest prime found on the diagonals is maxPrime = 11.
- Return 11.
Code for All Languages
C++
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
// Function to determine if a number is prime using precomputed sieve
bool isPrime(int num, vector<bool>& sieve) {
return sieve[num];
}
// Function to precompute primes up to a maximum value using Sieve of Eratosthenes
vector<bool> computeSieve(int maxVal) {
vector<bool> sieve(maxVal + 1, true);
sieve[0] = sieve[1] = false; // 0 and 1 are not prime
for (int i = 2; i * i <= maxVal; ++i) {
if (sieve[i]) {
for (int j = i * i; j <= maxVal; j += i) {
sieve[j] = false;
}
}
}
return sieve;
}
// Function to find the largest prime number on the diagonals
int diagonalPrime(vector<vector<int>>& nums) {
int n = nums.size();
int maxVal = 4 * 1000000; // Max value from the problem constraints
vector<bool> sieve = computeSieve(maxVal); // Precompute all primes
int maxPrime = 0; // Variable to store the largest prime found
for (int i = 0; i < n; ++i) {
// Check the primary diagonal element
if (isPrime(nums[i][i], sieve)) {
maxPrime = max(maxPrime, nums[i][i]);
}
// Check the secondary diagonal element
if (isPrime(nums[i][n - 1 - i], sieve)) {
maxPrime = max(maxPrime, nums[i][n - 1 - i]);
}
}
return maxPrime; // Return the largest prime found
}
};
int main() {
// User input driver
int n;
cin >> n; // Input size of the matrix
vector<vector<int>> nums(n, vector<int>(n));
// Input the matrix elements
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> nums[i][j];
}
}
// Create a Solution object and call the diagonalPrime function
Solution solution;
cout << solution.diagonalPrime(nums) << endl; // Output the result
return 0;
}
Java
import java.util.Scanner;
class Solution {
// Function to check if a number is prime using the precomputed sieve
private boolean isPrime(int num, boolean[] sieve) {
return sieve[num];
}
// Function to precompute primes using the Sieve of Eratosthenes
private boolean[] computeSieve(int maxVal) {
boolean[] sieve = new boolean[maxVal + 1];
for (int i = 0; i <= maxVal; i++) {
sieve[i] = true; // Initially, assume all numbers are prime
}
sieve[0] = false; // 0 is not prime
sieve[1] = false; // 1 is not prime
for (int i = 2; i * i <= maxVal; i++) {
if (sieve[i]) {
for (int j = i * i; j <= maxVal; j += i) {
sieve[j] = false; // Mark multiples of i as not prime
}
}
}
return sieve;
}
// Function to find the largest prime on the diagonals
public int diagonalPrime(int[][] nums) {
int n = nums.length;
int maxVal = 4 * 1000000; // Maximum value from the problem constraints
boolean[] sieve = computeSieve(maxVal); // Precompute all primes
int maxPrime = 0; // Variable to store the largest prime
for (int i = 0; i < n; i++) {
// Check the primary diagonal element
if (isPrime(nums[i][i], sieve)) {
maxPrime = Math.max(maxPrime, nums[i][i]);
}
// Check the secondary diagonal element
if (isPrime(nums[i][n - 1 - i], sieve)) {
maxPrime = Math.max(maxPrime, nums[i][n - 1 - i]);
}
}
return maxPrime; // Return the largest prime found
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input size of the matrix
int n = scanner.nextInt();
int[][] nums = new int[n][n];
// Input the matrix elements
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
nums[i][j] = scanner.nextInt();
}
}
// Create a Solution object and call the diagonalPrime function
Solution solution = new Solution();
System.out.println(solution.diagonalPrime(nums)); // Output the result
scanner.close();
}
}
Python
from typing import List
class Solution:
# Function to precompute primes using the Sieve of Eratosthenes
def compute_sieve(self, max_val: int) -> List[bool]:
sieve = [True] * (max_val + 1)
sieve[0] = sieve[1] = False # 0 and 1 are not prime
for i in range(2, int(max_val**0.5) + 1):
if sieve[i]:
for j in range(i * i, max_val + 1, i):
sieve[j] = False # Mark multiples of i as not prime
return sieve
# Function to find the largest prime on the diagonals
def diagonalPrime(self, nums: List[List[int]]) -> int:
n = len(nums)
max_val = 4 * 10**6 # Maximum value from the problem constraints
sieve = self.compute_sieve(max_val) # Precompute all primes
max_prime = 0 # Variable to store the largest prime
for i in range(n):
# Check the primary diagonal element
if sieve[nums[i][i]]:
max_prime = max(max_prime, nums[i][i])
# Check the secondary diagonal element
if sieve[nums[i][n - 1 - i]]:
max_prime = max(max_prime, nums[i][n - 1 - i])
return max_prime # Return the largest prime found
# Driver code
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0]) # First input is the size of the matrix
nums = [] # Initialize the matrix
index = 1
# Populate the matrix
for i in range(n):
row = list(map(int, data[index:index + n]))
nums.append(row)
index += n
# Create a Solution object and call the diagonalPrime function
solution = Solution()
print(solution.diagonalPrime(nums)) # Output the result
Javascript
function computeSieve(maxVal) {
const sieve = Array(maxVal + 1).fill(true);
sieve[0] = sieve[1] = false; // 0 and 1 are not prime numbers
for (let i = 2; i * i <= maxVal; i++) {
if (sieve[i]) {
for (let j = i * i; j <= maxVal; j += i) {
sieve[j] = false; // Mark multiples of i as not prime
}
}
}
return sieve;
}
var diagonalPrime = function(nums) {
const n = nums.length;
const maxVal = 4 * Math.pow(10, 6); // Maximum value from problem constraints
const sieve = computeSieve(maxVal); // Precompute primes
let maxPrime = 0; // Variable to track the largest prime
for (let i = 0; i < n; i++) {
// Check the primary diagonal element
if (sieve[nums[i][i]]) {
maxPrime = Math.max(maxPrime, nums[i][i]);
}
// Check the secondary diagonal element
if (sieve[nums[i][n - 1 - i]]) {
maxPrime = Math.max(maxPrime, nums[i][n - 1 - i]);
}
}
return maxPrime; // Return the largest prime found
};
// Driver code
const fs = require("fs");
const input = fs.readFileSync(0, "utf-8").trim().split("\n");
const n = parseInt(input[0]); // First input is the size of the matrix
const nums = [];
// Populate the matrix
for (let i = 1; i <= n; i++) {
nums.push(input[i].split(" ").map(Number));
}
// Call the function and print the result
console.log(diagonalPrime(nums));
Time Complexity : O(nlog(logn))
Precomputing Primes Using the Sieve of Eratosthenes
The sieve algorithm marks multiples of each number starting from 2 up to the square root of the largest value (4 * 10^6).
- For every number i, marking all its multiples takes O(n / i), where n = 4 * 10^6.
- Summing up for all i, the total time complexity of the sieve is O(n log log n).
Traversing the Diagonals
We traverse the matrix of size n x n, iterating over n rows:
- For each row i, we check two elements: the primary diagonal nums[i][i] and the secondary diagonal nums[i][n - 1 - i].
- Each check involves an O(1) lookup in the sieve array to determine if the number is prime.
Thus, this step takes O(n) time.
Final Time Complexity
- Precomputing primes: O(n log log n), where n = 4 * 10^6.
- Diagonal traversal: O(m), where m is the number of rows in the matrix.
- Overall time complexity: O(n log log n + m).
Since n = 4 * 10^6 and m ≤ 300, the sieve step dominates, resulting in a total time complexity of approximately O(n log log n).
Space Complexity : O(n + m²)
Auxiliary Space Complexity: O(n)
The auxiliary space includes:
- The sieve array of size n + 1, where n = 4 * 10^6, taking O(n) space.
- Constant space for variables such as largestPrime and loop counters, taking O(1) space.
Thus, the auxiliary space complexity is O(n).
Total Space Complexity: O(n + m²)
- The input matrix nums takes O(m²) space, where m is the size of the matrix.
- The sieve array for prime checking takes O(n) space, where n = 4 * 10^6.
Thus, the total space complexity is O(n + m²).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a 0-indexed two-dimensional integer array nums, return the largest prime number found on at least one of its diagonals. If no prime number is present on the diagonals, return 0. A prime number is greater than 1 and has no divisors other than 1 and itself.
Given an m x n matrix mat of integers, sort each diagonal of the matrix in ascending order and return the modified matrix. A diagonal is defined as a line of cells starting from any element in the topmost row or leftmost column, extending diagonally down to the right.