Check if Matrix Is X-Matrix
EasyAsked by:
33 views
Topics:
Arrays
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of values within the matrix?
- Can the matrix be rectangular (number of rows not equal to the number of columns), or is it always square?
- Can the matrix be empty, or have dimensions of zero?
- If a cell is on the diagonals, is it acceptable for it to also be zero, as long as *all* non-diagonal cells are zero?
- What data type should the matrix values be? Are they integers?
Brute Force Solution
Approach
We're given a grid and we need to check if it's an X-Matrix. The most straightforward way to do this is to examine every single spot in the grid and see if it follows the X-Matrix rules. We'll check each location to determine if it should be a certain value or a zero based on its position in the grid.
Here's how the algorithm would work step-by-step:
- Go through each position in the grid one by one.
- For each position, figure out if it's supposed to be on the main diagonals of the grid.
- If the position is on a diagonal, make sure it's not zero. If it is zero, then the grid is not an X-Matrix.
- If the position is not on a diagonal, make sure it's zero. If it's not zero, then the grid is not an X-Matrix.
- If we've checked every position and haven't found any problems, then the grid is an X-Matrix.
Code Implementation
def is_x_matrix(grid):
number_of_rows = len(grid)
number_of_columns = len(grid[0])
for row_index in range(number_of_rows):
for column_index in range(number_of_columns):
# Check if the current cell is on either diagonal
is_on_main_diagonal = row_index == column_index
is_on_anti_diagonal = row_index + column_index == number_of_rows - 1
if is_on_main_diagonal or is_on_anti_diagonal:
#Diagonals must not be zero
if grid[row_index][column_index] == 0:
return False
else:
#Off diagonals must be zero
if grid[row_index][column_index] != 0:
return False
# If all checks pass, it's an X-Matrix
return TrueBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through each cell of the n x n grid. For each of the n² cells, it performs a constant amount of work to check if the cell is on a diagonal and verify its value based on its position. Thus, the time complexity is proportional to the number of cells in the grid, which is n multiplied by n, resulting in n². Therefore, the overall time complexity is O(n²).
Space Complexity
O(1) – The provided algorithm iterates through the input matrix in place, examining each element without creating any auxiliary data structures like lists, arrays, or hash maps. It only uses a fixed number of variables, such as loop counters or boolean flags, to track the current position and the validity of the X-Matrix condition. Therefore, the space required does not depend on the size of the input matrix (N), and the space complexity is constant.
Optimal Solution
Approach
To check if a matrix is an X-Matrix efficiently, we focus only on the necessary cells. We verify that the diagonal cells have non-zero values, and all other cells have values of zero, skipping unnecessary checks.
Here's how the algorithm would work step-by-step:
- First, find the size of the matrix. We'll use this to identify diagonal cells.
- Check all the cells that form the two diagonals. Make sure each one has a value that is not zero.
- Now, go through every other cell in the matrix that isn't on the diagonals. Verify that each of these has a value of zero.
- If, after checking all the cells, every diagonal cell had a non-zero value and every other cell had a value of zero, then the matrix is an X-Matrix.
Code Implementation
def is_x_matrix(grid):
matrix_size = len(grid)
for row_index in range(matrix_size):
for column_index in range(matrix_size):
#Check diagonal elements
if row_index == column_index or row_index == matrix_size - column_index - 1:
if grid[row_index][column_index] == 0:
return False
# Check non-diagonal elements
else:
if grid[row_index][column_index] != 0:
return False
return TrueBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through the n x n matrix, where n is the number of rows (or columns, since it's a square matrix). It checks the diagonal elements (2n elements in total since it's both diagonals) and then iterates through the remaining elements in the matrix. The first part takes O(n) and the second part takes O(n² - n), which is iterating over the whole matrix excluding the diagonal. Since the constant factor and lower order terms are dropped, the dominant term n² determines the time complexity. Therefore, the overall time complexity is O(n²).
Space Complexity
O(1) – The algorithm iterates through the matrix, checking each cell based on its position relative to the diagonals. It uses only a few integer variables for indexing and comparison during the traversal. No auxiliary data structures like lists or hash maps are created to store intermediate results or visited cells. Therefore, the space used remains constant regardless of the matrix size (N), where N represents the number of rows and columns in the matrix, and the space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty matrix input | Return true if the matrix is null or empty, as an empty matrix technically satisfies the X-matrix condition (vacuously true). |
| Non-square matrix (rows != cols) | Return false immediately, since a non-square matrix cannot be an X-Matrix. |
| Matrix of size 1x1 | Return true if the single element is non-zero, and false otherwise. |
| Matrix with zero on the diagonals | Return false, as an X-Matrix must have non-zero values on the diagonals. |
| Matrix with non-zero value off the diagonals | Return false, as an X-Matrix must have zero values off the diagonals. |
| Large matrix size (N > 1000) | The solution should still execute efficiently with O(N^2) complexity, as it only iterates through the matrix once. |
| Matrix containing negative numbers | The solution is independent of the sign of the numbers, so negative numbers are handled correctly. |
| Matrix containing large integer values potentially leading to overflow | The algorithm only involves checking for equality with zero, so integer overflow is not a concern. |
Null or empty matrix input
How to Handle:
Return true if the matrix is null or empty, as an empty matrix technically satisfies the X-matrix condition (vacuously true).
Non-square matrix (rows != cols)
How to Handle:
Return false immediately, since a non-square matrix cannot be an X-Matrix.
Matrix of size 1x1
How to Handle:
Return true if the single element is non-zero, and false otherwise.
Matrix with zero on the diagonals
How to Handle:
Return false, as an X-Matrix must have non-zero values on the diagonals.
Matrix with non-zero value off the diagonals
How to Handle:
Return false, as an X-Matrix must have zero values off the diagonals.
Large matrix size (N > 1000)
How to Handle:
The solution should still execute efficiently with O(N^2) complexity, as it only iterates through the matrix once.
Matrix containing negative numbers
How to Handle:
The solution is independent of the sign of the numbers, so negative numbers are handled correctly.
Matrix containing large integer values potentially leading to overflow
How to Handle:
The algorithm only involves checking for equality with zero, so integer overflow is not a concern.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
