Check if Matrix Is X-Matrix

Easy

#2113Time: 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.

Data structures

Array Matrix

Prompt

A square matrix is said to be an X-Matrix if both of the following conditions hold:

All the elements in the diagonals of the matrix are non-zero.
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:

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⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean checkXMatrix(int[][] grid) {6        int n = grid.length;7        List<int[]> diagonalCoords = new ArrayList<>();8        List<int[]> nonDiagonalCoords = new ArrayList<>();9 10        // Step 1: Populate coordinate lists11        for (int i = 0; i < n; i++) {12            for (int j = 0; j < n; j++) {13                if (i == j || i + j == n - 1) {14                    diagonalCoords.add(new int[]{i, j});15                } else {16                    nonDiagonalCoords.add(new int[]{i, j});17                }18            }19        }20 21        // Step 2: Check diagonal elements22        for (int[] coord : diagonalCoords) {23            if (grid[coord[0]][coord[1]] == 0) {24                return false;25            }26        }27 28        // Step 3: Check non-diagonal elements29        for (int[] coord : nonDiagonalCoords) {30            if (grid[coord[0]][coord[1]] != 0) {31                return false;32            }33        }34 35        return true;36    }37}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

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

1class Solution {2    public boolean checkXMatrix(int[][] grid) {3        int n = grid.length;4        for (int i = 0; i < n; i++) {5            for (int j = 0; j < n; j++) {6                // Check if the element is on a diagonal7                if (i == j || i + j == n - 1) {8                    // Diagonal elements must be non-zero9                    if (grid[i][j] == 0) {10                        return false;11                    }12                } else {13                    // Non-diagonal elements must be zero14                    if (grid[i][j] != 0) {15                        return false;16                    }17                }18            }19        }20        return true;21    }22}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public bool CheckXMatrix(int[][] grid) {3        int n = grid.Length;4        for (int i = 0; i < n; ++i) {5            for (int j = 0; j < n; ++j) {6                if (i == j || i + j == n - 1) {7                    if (grid[i][j] == 0) {8                        return false;9                    }10                } else if (grid[i][j] != 0) {11                    return false;12                }13            }14        }15        return true;16    }17}

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem