Problem Description

An X-Matrix is a special type of square matrix that must satisfy two specific conditions:

1. All elements on both diagonals of the matrix must be non-zero
2. All other elements (not on the diagonals) must be 0

In a square matrix of size n x n:

• The main diagonal consists of elements where row index equals column index (i == j)
• The anti-diagonal consists of elements where row index plus column index equals n - 1 (i + j == n - 1)

Given a 2D integer array grid representing a square matrix of size n x n, you need to determine if it forms an X-Matrix.

Return true if the given grid is an X-Matrix, otherwise return false.

For example, in a 3x3 matrix, the diagonal positions would be:

• Main diagonal: positions (0,0), (1,1), (2,2)
• Anti-diagonal: positions (0,2), (1,1), (2,0)

All these positions must contain non-zero values, while positions like (0,1), (1,0), (1,2), (2,1) must contain zeros for the matrix to be considered an X-Matrix.

Intuition

The key insight is that we need to check every element in the matrix to verify if it meets the X-Matrix requirements. For each element at position (i, j), we can determine whether it should be non-zero or zero based on its position.

An element belongs to a diagonal if:

• It's on the main diagonal: when i == j (row index equals column index)
• It's on the anti-diagonal: when i + j == n - 1 (row plus column equals matrix size minus 1)

This observation leads to a straightforward checking strategy: iterate through each element and verify:

• If the element is on either diagonal (i == j or i + j == n - 1), it must be non-zero. If we find a zero here, the matrix fails the X-Matrix test.
• If the element is not on any diagonal, it must be zero. If we find a non-zero value here, the matrix fails the X-Matrix test.

The beauty of this approach is that we can combine both diagonal checks into a single condition using the OR operator, making the logic clean and efficient. We can immediately return false upon finding any violation, and only return true after confirming all elements satisfy their respective conditions.

Solution Approach

The solution implements a direct simulation approach by traversing the entire matrix and checking each element against the X-Matrix conditions.

Implementation Steps:

1. Iterate through the matrix: Use nested loops to traverse each element. The outer loop enumerate(grid) gives us the row index i and the row itself, while the inner loop enumerate(row) gives us the column index j and the value v at that position.

2. Check diagonal elements: For each position (i, j), determine if it's on a diagonal using the condition i == j or i + j == len(grid) - 1:

   • If the position is on a diagonal and the value is 0, immediately return False (violates the requirement that diagonal elements must be non-zero)

3. Check non-diagonal elements: If the position is not on any diagonal (the elif branch):

   • If the value v is non-zero (truthy in Python), immediately return False (violates the requirement that non-diagonal elements must be zero)

4. Return result: If we complete the traversal without finding any violations, return True indicating the matrix is a valid X-Matrix.

Key Pattern Used:

• Early termination: The algorithm returns False immediately upon finding the first violation, avoiding unnecessary checks
• Conditional checking: The use of if-elif structure elegantly handles the two mutually exclusive cases (diagonal vs non-diagonal positions)

The time complexity is O(n²) where n is the size of the matrix, as we visit each element exactly once. The space complexity is O(1) as we only use a constant amount of extra space for loop variables.

Example Walkthrough

Let's walk through the solution with a 3×3 matrix to see how we determine if it's an X-Matrix.

Example 1: Valid X-Matrix

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

Let's trace through each position:

1. Position (0,0), value = 2

   • Check: Is i == j or i + j == 2? → 0 == 0 is True (main diagonal)
   • Since it's on a diagonal and value is 2 (non-zero) ✓ Continue

2. Position (0,1), value = 0

   • Check: Is i == j or i + j == 2? → 0 != 1 and 0 + 1 != 2 → False
   • Since it's not on a diagonal and value is 0 ✓ Continue

3. Position (0,2), value = 7

   • Check: Is i == j or i + j == 2? → 0 != 2 but 0 + 2 == 2 is True (anti-diagonal)
   • Since it's on a diagonal and value is 7 (non-zero) ✓ Continue

4. Position (1,0), value = 0

   • Check: Is i == j or i + j == 2? → 1 != 0 and 1 + 0 != 2 → False
   • Since it's not on a diagonal and value is 0 ✓ Continue

5. Position (1,1), value = 5

   • Check: Is i == j or i + j == 2? → 1 == 1 is True (main diagonal)
   • Also note: 1 + 1 == 2 is True (anti-diagonal) - center element!
   • Since it's on a diagonal and value is 5 (non-zero) ✓ Continue

6. Position (1,2), value = 0

   • Check: Is i == j or i + j == 2? → 1 != 2 and 1 + 2 != 2 → False
   • Since it's not on a diagonal and value is 0 ✓ Continue

7. Position (2,0), value = 3

   • Check: Is i == j or i + j == 2? → 2 != 0 but 2 + 0 == 2 is True (anti-diagonal)
   • Since it's on a diagonal and value is 3 (non-zero) ✓ Continue

8. Position (2,1), value = 0

   • Check: Is i == j or i + j == 2? → 2 != 1 and 2 + 1 != 2 → False
   • Since it's not on a diagonal and value is 0 ✓ Continue

9. Position (2,2), value = 1

   • Check: Is i == j or i + j == 2? → 2 == 2 is True (main diagonal)
   • Since it's on a diagonal and value is 1 (non-zero) ✓ Continue

All checks passed! Return True.

Example 2: Invalid X-Matrix

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

Let's trace through until we find a violation:

1. Position (0,0), value = 5 → On main diagonal (0 == 0), non-zero ✓
2. Position (0,1), value = 7 → Not on any diagonal, but value is 7 (non-zero) ✗

The algorithm immediately returns False at position (0,1) because this position should contain 0 (it's not on any diagonal), but contains 7 instead.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the number of rows (or columns) of the matrix. This is because the code uses two nested loops - the outer loop iterates through each row (n iterations), and the inner loop iterates through each element in that row (n iterations for an n×n matrix). Therefore, the total number of operations is n × n = n².

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. The variables i, j, row, and v are the only additional variables created, and they don't scale with the size of the input matrix. The enumeration doesn't create additional data structures but rather provides iterators over the existing grid.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overlooking the Center Element in Odd-Sized Matrices

One common misconception is thinking that the center element in odd-sized matrices might need special handling since it belongs to both diagonals. Developers might write redundant code like:

# Unnecessary complex logic
if i == j and i + j == n - 1:  # Center element
    if value == 0:
        return False
elif i == j or i + j == n - 1:  # Other diagonal elements
    if value == 0:
        return False

Why it's a pitfall: This adds unnecessary complexity. The condition i == j or i + j == n - 1 already correctly handles the center element since it satisfies both conditions.

Solution: Trust the simple OR condition - it naturally handles all cases including the center element.

2. Using Wrong Diagonal Formula

A frequent error is using incorrect formulas for identifying diagonal positions:

# Incorrect anti-diagonal check
if i + j == n:  # Wrong! Should be n - 1
    # check for non-zero

Why it's a pitfall: The anti-diagonal formula i + j == n - 1 comes from the fact that in a 0-indexed matrix of size n, the sum of indices on the anti-diagonal equals n - 1, not n.

Solution: Remember that for 0-indexed arrays, the anti-diagonal condition is i + j == n - 1. Test with a small example: in a 3x3 matrix, position (0,2) should be on the anti-diagonal, and 0 + 2 = 2 = 3 - 1 ✓

3. Confusing Zero Check Logic

Developers sometimes mix up when to check for zero vs non-zero:

# Incorrect logic
if i == j or i + j == n - 1:
    if value != 0:  # Wrong! Should check if value == 0
        return False
else:
    if value == 0:  # Wrong! Should check if value != 0
        return False

Why it's a pitfall: The requirements are reversed - diagonals need non-zero values, non-diagonals need zeros.

Solution: Use clear variable names and comments. Consider using more explicit conditions:

on_diagonal = (i == j or i + j == n - 1)
if on_diagonal and value == 0:
    return False
if not on_diagonal and value != 0:
    return False

4. Not Handling Edge Cases

Some implementations might not consider edge cases like 1x1 matrices:

# Might cause issues with certain implementations
if n == 1:
    # Special handling needed?

Why it's a pitfall: Developers might think a 1x1 matrix needs special treatment since it has only one element that is both diagonals.

Solution: The general solution handles this correctly - a 1x1 matrix element at (0,0) satisfies both i == j and i + j == 0 == n - 1, so it just needs to be non-zero, which the standard logic already checks.