# Check if Matrix Is X-Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-matrix-is-x-matrix)
Canonical: https://scaleengineer.com/dsa/problems/check-if-matrix-is-x-matrix
**Data structures:** Array, Matrix
---
## Problem
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`.

**Example 1:**

![](https://assets.glich.co/dsa/check-if-matrix-is-x-matrix/image0.jpg) 

**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.

**Example 2:**

![](https://assets.glich.co/dsa/check-if-matrix-is-x-matrix/image1.jpg) 

**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] <= 105`

# Approaches
## Brute Force with Extra Space
This approach involves pre-calculating the coordinates of all diagonal and non-diagonal elements and storing them in separate data structures. It then iterates through these stored coordinates to check the matrix values against the X-Matrix conditions. While functionally correct, it's inefficient due to high memory usage.
**Time:** O(n^2). The first nested loop to populate the lists takes O(n^2). The subsequent loops iterate through O(n) and O(n^2) elements respectively. The total time is dominated by O(n^2). · **Space:** O(n^2). We store coordinates for all `n^2` elements in the matrix across two lists.
**Pros:** Separation of concerns: The logic for identifying positions is separate from the logic for validating values.; Easy to understand and debug due to the explicit separation of steps.
**Cons:** Highly inefficient in terms of space, using O(n^2) extra memory.; Unnecessary overhead of creating and managing lists of coordinates.; Multiple passes over the data (conceptually), which is less efficient than a single pass.
### Explanation
The core idea is to separate the identification of element positions from the validation of their values. We first iterate through all possible indices `(i, j)` of the `n x n` matrix. For each index, we determine if it lies on the main diagonal (`i == j`) or the anti-diagonal (`i + j == n - 1`). We maintain two lists of coordinates: one for diagonal elements and one for non-diagonal elements. After populating these lists, we perform two separate checks:
1. Iterate through the list of diagonal coordinates and verify that every corresponding element in the `grid` is non-zero. If we find a zero, we immediately return `false`.
2. Iterate through the list of non-diagonal coordinates and verify that every corresponding element in the `grid` is zero. If we find a non-zero value, we return `false`.
If both checks pass completely, it means the matrix satisfies the X-Matrix properties, and we return `true`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        List<int[]> diagonalCoords = new ArrayList<>();
        List<int[]> nonDiagonalCoords = new ArrayList<>();

        // Step 1: Populate coordinate lists
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i + j == n - 1) {
                    diagonalCoords.add(new int[]{i, j});
                } else {
                    nonDiagonalCoords.add(new int[]{i, j});
                }
            }
        }

        // Step 2: Check diagonal elements
        for (int[] coord : diagonalCoords) {
            if (grid[coord[0]][coord[1]] == 0) {
                return false;
            }
        }

        // Step 3: Check non-diagonal elements
        for (int[] coord : nonDiagonalCoords) {
            if (grid[coord[0]][coord[1]] != 0) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Get the dimension `n` of the matrix.
- Create two lists, `diagonalCoords` and `nonDiagonalCoords`, to store coordinates.
- Iterate from `i = 0` to `n-1` and `j = 0` to `n-1`:
    - If `i == j` or `i + j == n - 1`, add the coordinate `(i, j)` to `diagonalCoords`.
    - Otherwise, add `(i, j)` to `nonDiagonalCoords`.
- Iterate through each coordinate `(r, c)` in `diagonalCoords`:
    - If `grid[r][c]` is 0, return `false`.
- Iterate through each coordinate `(r, c)` in `nonDiagonalCoords`:
    - If `grid[r][c]` is not 0, return `false`.
- If all checks pass, return `true`.

## Optimal Single Pass Iteration
This is the most efficient approach. It involves iterating through the matrix just once. For each element, it simultaneously checks if it's on a diagonal and if its value adheres to the X-Matrix rules. This avoids any extra space and minimizes computation.
**Time:** O(n^2). We iterate through the `n x n` matrix exactly once. · **Space:** O(1). We only use a few variables for loop indices and the matrix size, not dependent on the input size.
**Pros:** Optimal time complexity, as every element must be visited in the worst case.; Optimal space complexity, using only constant extra space.; Concise and efficient implementation.
**Cons:** No significant cons, as this is the ideal solution for the problem.
### Explanation
The problem can be solved optimally by traversing the matrix a single time. We can use nested loops to visit every cell `grid[i][j]`. For each cell, we first determine its position relative to the diagonals. An element `grid[i][j]` is on a diagonal if its row index `i` is equal to its column index `j` (main diagonal), or if the sum of its indices `i + j` equals `n - 1` (anti-diagonal). We then apply the two conditions of an X-Matrix:
1. **If the element is on a diagonal (`i == j || i + j == n - 1`)**: Its value must be non-zero. If we find `grid[i][j] == 0`, we can immediately conclude the matrix is not an X-Matrix and return `false`.
2. **If the element is NOT on a diagonal**: Its value must be zero. If we find `grid[i][j] != 0`, we again know it's not an X-Matrix and return `false`.
If the loops complete without finding any violations, it means every element satisfies the conditions. Therefore, the matrix is an X-Matrix, and we can return `true`. This method is optimal because every element must be checked in the worst-case scenario, and this approach does so in a single pass with constant extra space.

```java
class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Check if the element is on a diagonal
                if (i == j || i + j == n - 1) {
                    // Diagonal elements must be non-zero
                    if (grid[i][j] == 0) {
                        return false;
                    }
                } else {
                    // Non-diagonal elements must be zero
                    if (grid[i][j] != 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Get the dimension `n` of the matrix.
- Iterate through each row `i` from `0` to `n-1`.
- Inside this loop, iterate through each column `j` from `0` to `n-1`.
- Check if the current element `grid[i][j]` is on a diagonal by checking the condition `i == j || i + j == n - 1`.
- If it is on a diagonal, check if `grid[i][j] == 0`. If it is, return `false`.
- If it is not on a diagonal, check if `grid[i][j] != 0`. If it is, return `false`.
- If the loops complete without returning `false`, return `true`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool CheckXMatrix(int[][] grid) {
        int n = grid.Length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || i + j == n - 1) {
                    if (grid[i][j] == 0) {
                        return false;
                    }
                } else if (grid[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}
```

### Java

```java
class Solution { public boolean checkXMatrix ( int [][] grid ) { int n = grid . length ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( i == j || i + j == n - 1 ) { if ( grid [ i ][ j ] == 0 ) { return false ; } } else if ( grid [ i ][ j ] != 0 ) { return false ; } } } return true ; } }
```

### CPP

```cpp
class Solution { public: bool checkXMatrix ( vector < vector < int >>& grid ) { int n = grid . size (); for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( i == j || i + j == n - 1 ) { if ( ! grid [ i ][ j ]) { return false ; } } else if ( grid [ i ][ j ]) { return false ; } } } return true ; } };
```

### Python

```python
class Solution : def checkXMatrix ( self , grid : List [ List [ int ]]) -> bool : for i , row in enumerate ( grid ): for j , v in enumerate ( row ): if i == j or i + j == len ( grid ) - 1 : if v == 0 : return False elif v : return False return True
```