LeetCode 2319 - Check if Matrix Is X-Matrix

The problem gives us a square matrix grid of size n x n. We must determine whether this matrix satisfies the definition of an X-Matrix. An X-Matrix has a very specific structure.

leetcodeeasyarraymatrix

LeetCode Problem 2319

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us a square matrix grid of size n x n. We must determine whether this matrix satisfies the definition of an X-Matrix.

An X-Matrix has a very specific structure. The two diagonals of the matrix must contain only non-zero values, and every other position must contain exactly 0.

The two diagonals are:

  • The main diagonal, where row == col
  • The secondary diagonal, where row + col == n - 1

Every cell belonging to either diagonal must be non-zero. Every cell that is not on either diagonal must be zero.

For example, in a 4 x 4 matrix:

X . . X
. X X .
. X X .
X . . X

The X positions are diagonal positions and must contain non-zero values. The . positions are non-diagonal positions and must contain 0.

The input is guaranteed to be a square matrix, so we do not need to validate dimensions. The constraints are relatively small:

  • 3 <= n <= 100
  • 0 <= grid[i][j] <= 10^5

Since the matrix size is at most 100 x 100, there are at most 10,000 cells. This means even a straightforward full traversal is easily fast enough.

There are several important edge cases to consider. A cell in the center of an odd-sized matrix belongs to both diagonals simultaneously. Such a cell only needs to satisfy the diagonal rule, meaning it must be non-zero. Another important case is when a diagonal element is 0, which immediately invalidates the matrix. Similarly, any non-diagonal element that is non-zero also invalidates the matrix.

Approaches

Brute Force Approach

The brute-force idea is to explicitly store all diagonal positions and then scan the matrix to validate every cell.

We can first identify all positions belonging to either diagonal by inserting them into a set. After that, we iterate through the matrix again. If a cell belongs to the diagonal set, we verify that it is non-zero. Otherwise, we verify that it is zero.

This approach is correct because every matrix cell is checked against the exact X-Matrix definition. However, it requires extra memory to store diagonal coordinates, which is unnecessary because diagonal membership can be computed directly using simple formulas.

Optimal Approach

The key observation is that we do not need any additional data structure to determine whether a cell belongs to a diagonal.

For any position (row, col):

  • It belongs to the main diagonal if row == col
  • It belongs to the secondary diagonal if row + col == n - 1

This allows us to determine diagonal membership in constant time while traversing the matrix once.

During the traversal:

  • If the current cell is on either diagonal, its value must be non-zero
  • Otherwise, its value must be zero

The moment we find a violation, we can immediately return false.

This approach is both simpler and more space-efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n²) Uses an additional set to store diagonal positions
Optimal O(n²) O(1) Checks diagonal membership directly during traversal

Algorithm Walkthrough

  1. Store the matrix size n.

We need the matrix size because the secondary diagonal condition depends on n - 1. 2. Traverse every cell in the matrix using nested loops.

The outer loop iterates through rows, and the inner loop iterates through columns. This guarantees that every matrix position is checked exactly once. 3. Determine whether the current cell belongs to a diagonal.

A cell (row, col) is a diagonal cell if either of these conditions is true:

  • row == col
  • row + col == n - 1
  1. Handle diagonal cells.

If the current cell is on a diagonal, its value must not be zero. If we encounter a zero diagonal value, we immediately return false. 5. Handle non-diagonal cells.

If the current cell is not on a diagonal, its value must be exactly zero. If we encounter a non-zero value outside the diagonals, we immediately return false. 6. Return true after the traversal finishes.

If every cell satisfies the required condition, then the matrix is a valid X-Matrix.

Why it works

The algorithm directly implements the mathematical definition of an X-Matrix. Every cell is classified into exactly one of two categories:

  • Diagonal cell
  • Non-diagonal cell

The algorithm verifies the correct rule for each category. Since every matrix position is checked exactly once and every violation causes immediate failure, the algorithm returns true if and only if the matrix satisfies the X-Matrix definition.

Python Solution

from typing import List

class Solution:
    def checkXMatrix(self, grid: List[List[int]]) -> bool:
        n = len(grid)

        for row in range(n):
            for col in range(n):
                is_diagonal = (row == col) or (row + col == n - 1)

                if is_diagonal:
                    if grid[row][col] == 0:
                        return False
                else:
                    if grid[row][col] != 0:
                        return False

        return True

The implementation begins by storing the matrix size in n. This is required for checking whether a position belongs to the secondary diagonal.

The nested loops iterate through every matrix cell exactly once. For each position, the variable is_diagonal determines whether the current cell belongs to either diagonal.

If the cell is diagonal, the code verifies that the value is non-zero. If the value is zero, the matrix violates the X-Matrix condition, so the function immediately returns False.

If the cell is not diagonal, the value must be exactly zero. Any non-zero value outside the diagonals immediately invalidates the matrix.

If the traversal completes without finding any violations, the matrix satisfies all requirements, so the function returns True.

Go Solution

func checkXMatrix(grid [][]int) bool {
    n := len(grid)

    for row := 0; row < n; row++ {
        for col := 0; col < n; col++ {
            isDiagonal := (row == col) || (row+col == n-1)

            if isDiagonal {
                if grid[row][col] == 0 {
                    return false
                }
            } else {
                if grid[row][col] != 0 {
                    return false
                }
            }
        }
    }

    return true
}

The Go implementation follows the same logic as the Python solution. Go slices are used to represent the matrix. Since the constraints are small and values fit comfortably within standard integer ranges, there are no overflow concerns.

Unlike Python, Go does not use type hints, but the function signature already specifies that grid is a two-dimensional integer slice.

Worked Examples

Example 1

grid = [
    [2,0,0,1],
    [0,3,1,0],
    [0,5,2,0],
    [4,0,0,2]
]

Here, n = 4.

The diagonal conditions are:

  • Main diagonal: (0,0), (1,1), (2,2), (3,3)
  • Secondary diagonal: (0,3), (1,2), (2,1), (3,0)
Position Value Diagonal? Expected Valid?
(0,0) 2 Yes Non-zero Yes
(0,1) 0 No Zero Yes
(0,2) 0 No Zero Yes
(0,3) 1 Yes Non-zero Yes
(1,0) 0 No Zero Yes
(1,1) 3 Yes Non-zero Yes
(1,2) 1 Yes Non-zero Yes
(1,3) 0 No Zero Yes
(2,0) 0 No Zero Yes
(2,1) 5 Yes Non-zero Yes
(2,2) 2 Yes Non-zero Yes
(2,3) 0 No Zero Yes
(3,0) 4 Yes Non-zero Yes
(3,1) 0 No Zero Yes
(3,2) 0 No Zero Yes
(3,3) 2 Yes Non-zero Yes

Every condition is satisfied, so the algorithm returns true.

Example 2

grid = [
    [5,7,0],
    [0,3,1],
    [0,5,0]
]

Here, n = 3.

Position Value Diagonal? Expected Valid?
(0,0) 5 Yes Non-zero Yes
(0,1) 7 No Zero No

The algorithm immediately detects that position (0,1) is not on a diagonal but contains 7. This violates the X-Matrix definition, so the function returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every matrix cell is visited exactly once
Space O(1) Only a few variables are used

The matrix contains n² elements, and each one is checked exactly once. No auxiliary data structures proportional to input size are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def checkXMatrix(self, grid: List[List[int]]) -> bool:
        n = len(grid)

        for row in range(n):
            for col in range(n):
                is_diagonal = (row == col) or (row + col == n - 1)

                if is_diagonal:
                    if grid[row][col] == 0:
                        return False
                else:
                    if grid[row][col] != 0:
                        return False

        return True

solution = Solution()

assert solution.checkXMatrix(
    [[2,0,0,1],
     [0,3,1,0],
     [0,5,2,0],
     [4,0,0,2]]
) == True  # Provided valid example

assert solution.checkXMatrix(
    [[5,7,0],
     [0,3,1],
     [0,5,0]]
) == False  # Provided invalid example

assert solution.checkXMatrix(
    [[1,0,1],
     [0,1,0],
     [1,0,1]]
) == True  # Small valid odd-sized matrix

assert solution.checkXMatrix(
    [[1,0,1],
     [0,0,0],
     [1,0,1]]
) == False  # Center belongs to both diagonals and cannot be zero

assert solution.checkXMatrix(
    [[1,1,1],
     [0,1,0],
     [1,0,1]]
) == False  # Non-diagonal element is non-zero

assert solution.checkXMatrix(
    [[0,0,1],
     [0,1,0],
     [1,0,1]]
) == False  # Main diagonal contains zero

assert solution.checkXMatrix(
    [[1,0,1,0],
     [0,1,0,1],
     [1,0,1,0],
     [0,1,0,1]]
) == False  # Several non-diagonal violations

assert solution.checkXMatrix(
    [[9,0,0,8],
     [0,7,6,0],
     [0,5,4,0],
     [3,0,0,2]]
) == True  # Larger valid matrix
Test Why
Valid 4x4 example Confirms correct handling of both diagonals
Invalid 3x3 example Detects non-zero value outside diagonals
Valid odd-sized matrix Verifies correct handling of center cell
Zero center cell Ensures shared diagonal center must be non-zero
Non-diagonal non-zero value Detects invalid off-diagonal elements
Zero on main diagonal Detects invalid diagonal elements
Multiple violations Ensures early detection still works
Larger valid matrix Confirms correctness on bigger inputs

Edge Cases

One important edge case occurs in odd-sized matrices because the center cell belongs to both diagonals simultaneously. A buggy implementation might accidentally treat this cell twice or apply conflicting logic. The current implementation avoids this issue because it simply checks whether the cell belongs to either diagonal using a single boolean condition. The center cell is therefore treated correctly as a diagonal element and only needs to be non-zero.

Another important edge case is when a diagonal element is zero. Since diagonal cells are required to contain non-zero values, even a single zero invalidates the matrix immediately. The implementation checks this condition as soon as a diagonal cell is encountered and returns False without unnecessary additional work.

A third important edge case is when a non-diagonal cell contains a non-zero value. This is easy to overlook if the implementation focuses only on validating diagonals. The algorithm explicitly checks every non-diagonal position and ensures it equals zero, guaranteeing that extra values outside the X shape are detected correctly.

A final edge case involves the smallest allowed matrix size, which is 3 x 3. Small matrices often expose indexing mistakes or incorrect diagonal calculations. The formula row + col == n - 1 works correctly even at the smallest valid size, ensuring reliable behavior across all allowed inputs.