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.
This approach involves iterating over every element of the matrix and evaluating their positions. For elements on the main or anti-diagonal, ensure they are non-zero. For other elements, check if they are zero.
This C function iterates across the entire grid. For each element, it checks if the element is on the main diagonal (i == j) or the anti-diagonal (i + j == gridSize - 1). If so, it ensures the element is non-zero. Elements not on these diagonals are checked to be zero. If the conditions break at any point, it returns false.
Time Complexity: O(n^2) where n is the number of rows (or columns) in the matrix. Space Complexity: O(1), only constant space is used.
This approach explicitly checks nodes based on their positions. First, identify and validate values on the diagonals, then on the fly, verify if non-diagonal elements maintain zero-value constraints.
This optimized C method checks elements by evaluating if they reside on any diagonals according to its conditions then checks if invalid conditions are met early. This enables early termination of the check if any rule is breached.
Time Complexity: O(n^2), efficiently checks all node conditions with a potential early stop. Space Complexity: O(1), only uses base iterative space without extra structures.
We can directly traverse the matrix and check if each element satisfies the conditions of an X matrix. If any element does not satisfy the conditions, return false immediately. If all elements satisfy the conditions after traversal, return true.
The time complexity is O(n^2), where n is the number of rows or columns of the matrix. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n^2) where n is the number of rows (or columns) in the matrix. Space Complexity: O(1), only constant space is used. |
| Separate Diagonal and Non-Diagonal Check | Time Complexity: O(n^2), efficiently checks all node conditions with a potential early stop. Space Complexity: O(1), only uses base iterative space without extra structures. |
| Simulation | — |
| 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. |
Weekly Contest 299 | Leetcode 2319 Check if Matrix Is X-Matrix 🔥🔥 | Matrix | Easy Peasy • Coding Decoded • 879 views views
Watch 9 more video solutions →Practice Check if Matrix Is X-Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor