Check if Matrix Is X-Matrix — Solution in Python, Java & C++
Check if Matrix Is X-Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check if Matrix Is X-Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A square matrix is an X-Matrix when both hold:
- Every element on one of the two main diagonals is non-zero.
- Every other element is zero.
Given a square matrix grid, return true if it is an X-Matrix.
Example 1
Input: grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
Output: true
Example 2
Input: grid = [[5,7,0],[0,3,1],[0,5,0]]
Output: false
Explanation: The 7 sits off both diagonals but is non-zero.
Example 3
Input: grid = [[1]]
Output: true
Constraints
1 <= grid.length <= 8grid[i].length == grid.length0 <= grid[i][j] <= 100000
Hints for Check if Matrix Is X-Matrix
Hint 1
A cell
(r, c)is on a diagonal exactly whenr == corr + c == n - 1.Hint 2
One pass over every cell checks both rules with a single branch.
Hint 3
The centre of an odd-sized matrix satisfies both conditions at once — it is still just a diagonal cell.
How to solve Check if Matrix Is X-Matrix
A cell is on a diagonal iff r == c or r + c == n - 1; diagonal cells must be non-zero and every other cell must be zero.
Approach
- For each cell compute
onDiagonal. - Return
falseif a diagonal cell is 0 or a non-diagonal cell is non-zero. - Return
true.
Why it works
The two conditions partition the cells, so one pass with a single branch checks both rules.
Complexity
- Time —
O(n²) - Space —
O(1)
Pitfalls
- The centre of an odd-sized matrix satisfies both diagonal tests; it is still just a diagonal cell.
Reference solution
Python
def checkXMatrix(grid) -> bool:
n = len(grid)
for r in range(n):
for c in range(n):
on_diagonal = r == c or r + c == n - 1
if on_diagonal and grid[r][c] == 0:
return False
if not on_diagonal and grid[r][c] != 0:
return False
return TrueJava
public static boolean checkXMatrix(int[][] grid) {
int n = grid.length;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
boolean onDiagonal = r == c || r + c == n - 1;
if (onDiagonal && grid[r][c] == 0) return false;
if (!onDiagonal && grid[r][c] != 0) return false;
}
}
return true;
}C++
bool checkXMatrix(vector<vector<int>>& grid) {
int n = (int) grid.size();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
bool onDiagonal = r == c || r + c == n - 1;
if (onDiagonal && grid[r][c] == 0) return false;
if (!onDiagonal && grid[r][c] != 0) return false;
}
}
return true;
}JavaScript
var checkXMatrix = function(grid) {
const n = grid.length;
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
const onDiagonal = r === c || r + c === n - 1;
if (onDiagonal && grid[r][c] === 0) return false;
if (!onDiagonal && grid[r][c] !== 0) return false;
}
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal