A square matrix is said to be an X-Matrix if both of the following conditions hold:
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].length3 <= n <= 1000 <= grid[i][j] <= 105To solve #2319 Check if Matrix Is X-Matrix, the key idea is to validate the values along the matrix diagonals and ensure all other cells are zero. In an X-matrix, both the primary diagonal (i == j) and the secondary diagonal (i + j == n - 1) must contain non-zero values, while every other position must contain 0.
A straightforward approach is to iterate through every cell of the n x n matrix using nested loops. For each position, check whether it belongs to one of the diagonals. If it is a diagonal cell, verify that the value is not zero. Otherwise, ensure the value is zero. If any condition fails, the matrix cannot be considered an X-matrix.
This method works efficiently because each element is visited exactly once. The algorithm runs in O(n²) time with O(1) extra space, making it optimal for this problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single pass matrix traversal | O(n^2) | O(1) |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
Assuming a 0-indexed matrix, for a given cell on row i and column j, it is in a diagonal if and only if i == j or i == n - 1 - j.
We can then iterate through the elements in the matrix to check if all the elements in the diagonals are non-zero and all other elements are zero.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
A cell belongs to the primary diagonal when row and column indices are equal (i == j). It belongs to the secondary diagonal when the sum of indices equals n - 1 (i + j == n - 1). These two conditions help determine whether the value should be non-zero.
Problems like this are common in coding interviews because they test matrix traversal and index logic. While the exact question may vary, similar diagonal or matrix validation problems frequently appear in technical screening rounds.
A 2D array (matrix) is sufficient since the problem directly operates on matrix indices. No additional data structures are required because the diagonal conditions can be checked using index comparisons.
The optimal approach is to traverse the matrix once and check each cell's position. If the cell lies on either diagonal, it must be non-zero; otherwise it must be zero. This ensures correctness with a simple O(n^2) scan and constant extra space.