Check if Matrix Is X-Matrix
Problem Description
A square matrix is said to be an X-Matrix if both of the following conditions hold:
1. All the elements in the diagonals of the matrix are non-zero.
2. All other elements are 0.
Given a 2D integer array grid of size n x n representing a square matrix, return true if grid is an X-Matrix. Otherwise, return false.
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: grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
Output: true
Explanation: Refer to the diagram above.
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0. Thus, grid is an X-Matrix.
Input: grid = [[5,7,0],[0,3,1],[0,5,0]]
Output: false
Explanation: Refer to the diagram above.
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0. Thus, grid is not an X-Matrix.
Constraints
- n == grid.length == grid[i].length
- 3 <= n <= 100
- 0 <= grid[i][j] <= 10^5
The initial idea is to traverse the matrix and check if it meets the conditions of an X-Matrix. The key focus is to clearly distinguish between diagonal and non-diagonal indices. Let’s explore how we can approach this.
Optimal Approach
Intuition
The main task for us is to identify the diagonal indices, which consists of both the primary and secondary diagonal. Both this diagonals together form the "X", that's why it is called an X-Matrix. Let's see how to identify these elements
How to Identify Diagonal Elements?
The tricky part here is identifying which elements belong to the diagonals. Let’s break it down:
Primary Diagonal:
In the primary diagonal, the row index is equal to the column index. For example:
- In mat[0][0], row = 0 and column = 0 → It's a primary diagonal element.
- In mat[1][1], row = 1 and column = 1 → It's a primary diagonal element.
In general, any element mat[i][i] belongs to the primary diagonal.
Secondary Diagonal:
In the secondary diagonal, the row index + column index = size of the matrix - 1. For example:
- In mat[0][2], row = 0, column = 2 → 0 + 2 = 2, which equals size - 1 for a 3x3 matrix.
- In mat[1][1], row = 1, column = 1 → 1 + 1 = 2, which equals size - 1.
In general, any element mat[i][n - 1 - i] (where n is the size of the matrix) belongs to the secondary diagonal.
What if an element belongs to both diagonals:
For such elements, there’s no issue since the problem does not require us to differentiate them. We just need to check that the element is non-zero. The fact that it belongs to both diagonals does not affect the logic because the condition is the same for both diagonals: the element must be non-zero.
Now that we know how to identify the diagonal elements, let’s think about the remaining elements in the matrix. If an element is not part of the primary or secondary diagonal, it is a non-diagonal element. These are the elements outside the "X" formed by the diagonals.
Once we can distinguish between diagonal and non-diagonal elements, the problem becomes simpler. We just need to check two conditions: all diagonal elements must be non-zero, and all non-diagonal elements must be zero. This way, we can methodically verify if the given matrix satisfies the requirements of an X-Matrix.
Approach
Step 1: Traverse the entire matrix
To check each element in the matrix, we need to go row by row and column by column. Use a loop to go through each row index, and within that, another loop to go through each column index. This ensures every element of the matrix is checked.
Step 2: Identify diagonal elements
While traversing the matrix, we need to determine if the current element belongs to either the primary or secondary diagonal.
- For the primary diagonal, check if the row index is equal to the column index.
- For the secondary diagonal, check if the sum of the row and column indices is equal to the size of the matrix minus one.
If either of these conditions is true, the element is part of the diagonal.
Step 3: Check the condition for diagonal elements
If an element belongs to a diagonal, its value must be non-zero. Check the value of the diagonal element, and if it is zero, immediately stop the process and return false, since the matrix cannot be an X-Matrix.
Step 4: Identify non-diagonal elements
If an element does not satisfy the conditions for being part of either diagonal, it is a non-diagonal element. For these elements, ensure their value is exactly zero. If any non-diagonal element is found to be non-zero, immediately stop the process and return false.
Step 5: Complete the traversal
Continue checking all elements in the matrix using the loops. If the traversal completes without finding any violations (diagonal element being zero or non-diagonal element being non-zero), then the matrix satisfies the conditions of an X-Matrix.
Step 6: Return the result
If no violations are found, return true, indicating that the matrix is an X-Matrix. If any condition fails during the traversal, return false.
Dry Run
Input : grid = [[2, 0, 0, 1], [0, 3, 1, 0], [0, 5, 2, 0], [4, 0, 0, 2]].
The size of the matrix is 4 x 4, so the value of n is 4.
Step 1: Start with the first row
The first row is [2, 0, 0, 1].
- Check the element at position (0, 0). Since the row index is 0 and the column index is also 0, it is part of the primary diagonal. The value is 2, which is non-zero, so it satisfies the condition.
- Check the element at position (0, 1). It is not part of either the primary diagonal or the secondary diagonal because 0 is not equal to 1, and 0 + 1 is not equal to n - 1 (which is 3). It is a non-diagonal element, and its value is 0, so it satisfies the condition.
- Check the element at position (0, 2). Similar to (0, 1), this is a non-diagonal element, and its value is 0, so it satisfies the condition.
- Check the element at position (0, 3). Here, 0 + 3 equals n - 1 (which is 3), so it is part of the secondary diagonal. The value is 1, which is non-zero, so it satisfies the condition.
The first row satisfies all conditions.
Step 2: Move to the second row
The second row is [0, 3, 1, 0].
- Check the element at position (1, 0). This is not part of either diagonal, as 1 is not equal to 0, and 1 + 0 is not equal to 3. It is a non-diagonal element, and its value is 0, so it satisfies the condition.
- Check the element at position (1, 1). Here, 1 equals 1, so it is part of the primary diagonal. The value is 3, which is non-zero, so it satisfies the condition.
- Check the element at position (1, 2). Here, 1 + 2 equals 3, so it is part of the secondary diagonal. The value is 1, which is non-zero, so it satisfies the condition.
- Check the element at position (1, 3). This is a non-diagonal element because 1 is not equal to 3, and 1 + 3 is not equal to 3. Its value is 0, so it satisfies the condition.
The second row satisfies all conditions.
Step 3: Move to the third row
The third row is [0, 5, 2, 0].
- Check the element at position (2, 0). This is a non-diagonal element because 2 is not equal to 0, and 2 + 0 is not equal to 3. Its value is 0, so it satisfies the condition.
- Check the element at position (2, 1). Here, 2 + 1 equals 3, so it is part of the secondary diagonal. The value is 5, which is non-zero, so it satisfies the condition.
- Check the element at position (2, 2). Here, 2 equals 2, so it is part of the primary diagonal. The value is 2, which is non-zero, so it satisfies the condition.
- Check the element at position (2, 3). This is a non-diagonal element because 2 is not equal to 3, and 2 + 3 is not equal to 3. Its value is 0, so it satisfies the condition.
The third row satisfies all conditions.
Step 4: Move to the fourth row
The fourth row is [4, 0, 0, 2].
- Check the element at position (3, 0). Here, 3 + 0 equals 3, so it is part of the secondary diagonal. The value is 4, which is non-zero, so it satisfies the condition.
- Check the element at position (3, 1). This is a non-diagonal element because 3 is not equal to 1, and 3 + 1 is not equal to 3. Its value is 0, so it satisfies the condition.
- Check the element at position (3, 2). This is a non-diagonal element because 3 is not equal to 2, and 3 + 2 is not equal to 3. Its value is 0, so it satisfies the condition.
- Check the element at position (3, 3). Here, 3 equals 3, so it is part of the primary diagonal. The value is 2, which is non-zero, so it satisfies the condition.
The fourth row satisfies all conditions.
We have checked all rows of the matrix. Every diagonal element is non-zero, and every non-diagonal element is zero. Therefore, the matrix satisfies the conditions of an X-Matrix. The output is true.
Code for All Languages
C++
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool checkXMatrix(vector<vector<int>>& grid) {
// Get the size of the matrix (n x n)
int n = grid.size();
// Traverse the matrix to check the conditions
for (int row = 0; row < n; ++row) {
for (int col = 0; col < n; ++col) {
// Check for diagonal elements
if (row == col || col == n - 1 - row) {
// If it's a diagonal element, it should be non-zero
if (grid[row][col] == 0) {
return false; // Return false if diagonal element is zero
}
} else {
// If it's not a diagonal element, it should be zero
if (grid[row][col] != 0) {
return false; // Return false if non-diagonal element is non-zero
}
}
}
}
// Return true if all conditions are satisfied
return true;
}
};
int main() {
int n;
// Read the size of the matrix (n x n)
cin >> n;
// Create an n x n matrix
vector<vector<int>> grid(n, vector<int>(n));
// Input the matrix elements
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> grid[i][j];
}
}
// Create an object of Solution class and check if the matrix is an X-Matrix
Solution solution;
bool result = solution.checkXMatrix(grid);
// Output the result
if (result) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
Java
import java.util.Scanner;
class Solution {
public boolean checkXMatrix(int[][] grid) {
// Get the size of the matrix (n x n)
int n = grid.length;
// Traverse the matrix to check the conditions
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
// Check for diagonal elements
if (row == col || col == n - 1 - row) {
// If it's a diagonal element, it should be non-zero
if (grid[row][col] == 0) {
return false; // Return false if diagonal element is zero
}
} else {
// If it's not a diagonal element, it should be zero
if (grid[row][col] != 0) {
return false; // Return false if non-diagonal element is non-zero
}
}
}
}
// Return true if all conditions are satisfied
return true;
}
public static void main(String[] args) {
// Create a scanner to take user input
Scanner sc = new Scanner(System.in);
// Read the size of the matrix (n x n)
int n = sc.nextInt();
// Create an n x n matrix
int[][] grid = new int[n][n];
// Input the matrix elements
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = sc.nextInt();
}
}
// Create an object of Solution class and check if the matrix is an X-Matrix
Solution solution = new Solution();
boolean result = solution.checkXMatrix(grid);
// Output the result
if (result) {
System.out.println("true");
} else {
System.out.println("false");
}
// Close the scanner
sc.close();
}
}
Python
from typing import List
class Solution:
def checkXMatrix(self, grid: List[List[int]]) -> bool:
# Get the size of the matrix (n x n)
n = len(grid)
# Traverse the matrix to check the conditions
for row in range(n):
for col in range(n):
# Check for diagonal elements
if row == col or col == n - 1 - row:
# If it's a diagonal element, it should be non-zero
if grid[row][col] == 0:
return False # Return False if diagonal element is zero
else:
# If it's not a diagonal element, it should be zero
if grid[row][col] != 0:
return False # Return False if non-diagonal element is non-zero
# Return True if all conditions are satisfied
return True
# Driver code to take input and check if the matrix is an X-Matrix
if __name__ == "__main__":
# Input the size of the matrix (n x n)
n = int(input())
# Create an empty n x n matrix
grid = []
# Input the matrix elements
for i in range(n):
row = list(map(int, input().split()))
grid.append(row)
# Create an object of Solution class and check if the matrix is an X-Matrix
solution = Solution()
result = solution.checkXMatrix(grid)
# Output the result
if result:
print("true")
else:
print("false")
Javascript
var checkXMatrix = function(grid) {
// Get the size of the matrix (n x n)
let n = grid.length;
// Traverse the matrix to check the conditions
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
// Check for diagonal elements
if (row === col || col === n - 1 - row) {
// If it's a diagonal element, it should be non-zero
if (grid[row][col] === 0) {
return false; // Return false if diagonal element is zero
}
} else {
// If it's not a diagonal element, it should be zero
if (grid[row][col] !== 0) {
return false; // Return false if non-diagonal element is non-zero
}
}
}
}
// Return true if all conditions are satisfied
return true;
};
// Driver code to take input and check if the matrix is an X-Matrix
const n = parseInt(prompt());
let grid = [];
for (let i = 0; i < n; i++) {
let row = prompt().split(" ").map(Number);
grid.push(row);
}
let result = checkXMatrix(grid);
console.log(result ? "true" : "false");
Time Complexity : O(n)
Loop Execution
We loop over each row of the matrix, which runs n times (where n is the size of the matrix). In each iteration, we check if the current element belongs to either the primary or secondary diagonal and verify its value. This involves simple index comparisons and value checks, which are done in constant time O(1) for each element.
Thus, for each of the n rows, we perform constant time operations, and the total number of operations is proportional to the size of the matrix.
Final Time Complexity
The overall time complexity is O(n), where n is the number of rows (or columns) in the matrix. This is because we iterate through each row of the matrix once and perform constant time operations for each element.
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space refers to the extra space used by the algorithm aside from the input. In this case, we are using only a few variables: n (size of the matrix), and a few other variables for iteration and checking conditions. These variables require constant space, O(1).
Total Space Complexity: O(n^2)
The total space includes both the input (the matrix) and the auxiliary space.
The input matrix grid takes O(n^2) space, as it is an n x n matrix.
The algorithm does not use any additional space proportional to the size of the input, except for the few constant variables.
Therefore, the overall space complexity is dominated by the size of the input matrix, which is O(n^2).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a square matrix mat, return the sum of the matrix diagonals.
Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.
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.