Watch 10 video solutions for Check if Matrix Is X-Matrix, a easy level problem involving Array, Matrix. This walkthrough by Coding Decoded has 879 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem Overview: You are given an n x n matrix. The matrix is considered an X-Matrix if every element on the primary diagonal (i == j) and secondary diagonal (i + j == n - 1) is non‑zero, and every other element is exactly zero. The task is to verify these conditions for all cells in the matrix.
Approach 1: Iterative Matrix Traversal (O(n^2) time, O(1) space)
Traverse the entire matrix using two nested loops. For each cell (i, j), determine whether it lies on one of the two diagonals. If i == j or i + j == n - 1, the value must be non‑zero. If the cell is not on either diagonal, the value must be zero. The moment a violation appears, return false. This approach works because every cell is validated exactly once, and the diagonal condition is computed with constant-time checks.
This solution uses straightforward iteration over a matrix and simple conditional checks. Since no extra data structures are required, the space usage remains constant. The runtime is O(n^2) because every element in the matrix must be inspected.
Approach 2: Separate Diagonal and Non-Diagonal Checks (O(n^2) time, O(1) space)
Another way to structure the validation is to handle diagonal and non-diagonal cells separately. First iterate through indices i and check the primary diagonal grid[i][i] and secondary diagonal grid[i][n - i - 1]. Both values must be non-zero. After confirming the diagonals, run a second pass through the matrix to verify that every remaining cell is zero.
This separation makes the logic slightly clearer in interviews because the X-structure is validated in two explicit phases. It still relies on basic array traversal and index math. The overall time complexity remains O(n^2) since the matrix is scanned, and the space complexity is O(1).
Recommended for interviews: The single-pass iterative traversal is usually preferred. It validates diagonal and non-diagonal conditions in one loop, keeps the implementation concise, and avoids redundant scans. The two-phase version is still acceptable and sometimes easier to reason about, but interviewers typically expect the clean single-pass matrix check once you recognize the diagonal conditions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Matrix Traversal | O(n^2) | O(1) | Best general solution. Validates all constraints in a single pass. |
| Separate Diagonal and Non-Diagonal Check | O(n^2) | O(1) | Useful when you want clearer logic by validating diagonals first, then remaining cells. |