Weekly Contest 299 | Leetcode 2319 Check if Matrix Is X-Matrix 🔥🔥 | Matrix | Easy Peasy
Check if Matrix Is X-Matrix - Video Solution
Watch 10 video solutions for Check if Matrix Is X-Matrix, a easy level problem involving Array, Matrix. This walkthrough by Coding Decoded has 903 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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].length3 <= n <= 1000 <= grid[i][j] <= 105
Approach Overview
Problem 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.
Complexity Analysis
| 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. |