Check if Matrix Is X-Matrix

Difficulty: Easy | Acceptance: 66.60% | Paid: No Topics: Array, Matrix

A square matrix is said to be an X-Matrix if both 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.

• Examples
• Constraints
• Single Pass Simulation
• Two-Pass Validation
• Hash Set of Diagonal Indices

Examples

Example 1:

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:

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⁵

Single Pass Simulation

Intuition We iterate through every cell in the matrix once. For each cell, we determine if it lies on a diagonal using mathematical indices. If it is on a diagonal, it must be non-zero; otherwise, it must be zero.

Steps

• Get the size of the matrix n.
• Loop through each row i from 0 to n-1.
• Loop through each column j from 0 to n-1.
• Check if the current cell (i, j) is on the main diagonal (i == j) or the anti-diagonal (i + j == n - 1).
• If it is on a diagonal and the value is 0, return false.
• If it is not on a diagonal and the value is not 0, return false.
• If the loops complete without returning false, return true.

from typing import List

class Solution:
    def checkXMatrix(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if i == j or i + j == n - 1:
                    if grid[i][j] == 0:
                        return False
                else:
                    if grid[i][j] != 0:
                        return False
        return True

Complexity

• Time: O(n²) — We visit every element in the n x n matrix exactly once.
• Space: O(1) — We only use a few variables for indices and size.
• Notes: This is the most optimal approach in terms of both time and space complexity.

Two-Pass Validation

Intuition We separate the validation logic into two distinct passes. First, we verify that all diagonal elements are non-zero. Then, we verify that all non-diagonal elements are zero. This can sometimes be easier to reason about or optimize if one condition fails early.

Steps

• Get the size of the matrix n.
• Pass 1: Iterate i from 0 to n-1. Check grid[i][i] (main diagonal) and grid[i][n-1-i] (anti-diagonal). If any are 0, return false.
• Pass 2: Iterate through all cells (i, j). If the cell is not on a diagonal and the value is not 0, return false.
• If both passes complete, return true.

from typing import List

class Solution:
    def checkXMatrix(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        # Check diagonals
        for i in range(n):
            if grid[i][i] == 0 or grid[i][n - 1 - i] == 0:
                return False
        # Check non-diagonals
        for i in range(n):
            for j in range(n):
                if i != j and i + j != n - 1:
                    if grid[i][j] != 0:
                        return False
        return True

Complexity

• Time: O(n²) — In the worst case, we traverse the entire matrix.
• Space: O(1) — No extra space is used.
• Notes: While the time complexity is the same, this approach might perform slightly worse if the matrix is large and valid, as it iterates over diagonal elements twice (once in the first pass and once in the second pass).

Hash Set of Diagonal Indices

Intuition We can pre-calculate all the coordinates of the diagonal cells and store them in a set. Then, we iterate through the matrix. If a cell’s coordinates are in the set, we check for non-zero; otherwise, we check for zero. This trades some space for potentially simpler conditional logic inside the loop.

Steps

• Get the size of the matrix n.
• Create an empty set to store diagonal coordinates.
• Iterate i from 0 to n-1. Add (i, i) and (i, n-1-i) to the set.
• Iterate through all cells (i, j).
• If (i, j) is in the set and grid[i][j] == 0, return false.
• If (i, j) is not in the set and grid[i][j] != 0, return false.
• Return true.

from typing import List, Set, Tuple

class Solution:
    def checkXMatrix(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        diagonals: Set[Tuple[int, int]] = set()
        for i in range(n):
            diagonals.add((i, i))
            diagonals.add((i, n - 1 - i))
        for i in range(n):
            for j in range(n):
                if (i, j) in diagonals:
                    if grid[i][j] == 0:
                        return False
                else:
                    if grid[i][j] != 0:
                        return False
        return True

Complexity

• Time: O(n²) — We iterate through the matrix to build the set (O(n)) and then to check values (O(n²)).
• Space: O(n) — The set stores 2n coordinates (minus the center overlap), so the space complexity is linear relative to the dimension.
• Notes: This approach is less space-efficient than the mathematical check but demonstrates how to trade space for lookup speed or code clarity in more complex scenarios.