#2319

Easy

LeetCode Problem Workspace

Check if Matrix Is X-Matrix

Check if a square matrix follows the X-Matrix pattern by validating diagonal and non-diagonal conditions.

Problem Statement

You are given a square matrix represented by a 2D array of integers. An X-Matrix is defined as a matrix where both diagonals contain non-zero elements, and all non-diagonal elements must be zero.

Write a function that returns true if the given matrix is an X-Matrix and false otherwise. The matrix has a size of n x n, where 3 <= n <= 100, and matrix elements are between 0 and 105.

Examples

Example 1

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

Output: true

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

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

Solution Approach

Diagonal Check

For each element in the matrix, check if it lies on either of the two diagonals: top-left to bottom-right (i == j) or top-right to bottom-left (i == n - 1 - j). Ensure all diagonal elements are non-zero.

Non-Diagonal Zero Check

For all elements that are not on the diagonals, check if they are equal to zero. If any non-diagonal element is non-zero, the matrix cannot be an X-Matrix.

Iterate through the Matrix

Loop through each row and column of the matrix, checking the diagonal and non-diagonal conditions. Return false as soon as a discrepancy is found, and return true if all conditions hold.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n^2) due to the need to traverse each element of the n x n matrix. The space complexity is O(1) as we only need a few variables to track the checks, without requiring additional space.

What Interviewers Usually Probe

Candidate demonstrates understanding of matrix traversal and diagonal checking.
Look for an efficient solution that iterates through the matrix once, checking both conditions.
Candidate should handle edge cases, such as matrices where all elements are zero or matrices that are clearly non-X-Matrices.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the diagonal pattern or incorrectly checking non-diagonal elements.
Over-complicating the solution by requiring additional space when O(1) space is sufficient.
Not accounting for all matrix elements in the check, leading to incorrect results.

Follow-up variants

Adjust the problem to consider non-square matrices or non-integer elements.
Implement additional constraints like handling large grids efficiently.
Consider edge cases where the matrix has the minimum size (3x3) or elements are at their maximum values.

FAQ

What is an X-Matrix?

An X-Matrix is a square matrix where the diagonals contain non-zero elements and all non-diagonal elements are zero.

How can I check if a matrix is an X-Matrix?

To check, iterate through the matrix, ensure diagonals contain non-zero elements, and all non-diagonal elements are zero.

What is the time complexity of this problem?

The time complexity is O(n^2) because the solution involves checking each element of the n x n matrix.

Can a matrix with all zero elements be an X-Matrix?

No, a matrix with all zero elements cannot be an X-Matrix because the diagonals need to have non-zero values.

What is the space complexity for solving this problem?

The space complexity is O(1), as the solution only requires a few variables to track the checks, without needing extra space.

terminal

Solution

Solution 1: Simulation

We can directly traverse the matrix and check if each element satisfies the conditions of an $X$ matrix. If any element does not satisfy the conditions, return $\textit{false}$ immediately. If all elements satisfy the conditions after traversal, return $\textit{true}$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2326 spiral matrix iv #2328 number of increasing paths in a grid #2304 minimum path cost in a grid