Jobs

Interviews

Discussions

Check if Matrix Is X-Matrix

Easy

Google

2 views

Topics:

Arrays

Problem

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.

Examples

For example, the grid below is an X-Matrix, so return true

[[2,0,0,1],
 [0,3,1,0],
 [0,5,2,0],
 [4,0,0,2]]

In the grid below is not an X-Matrix, return false

[[5,7,0],
 [0,3,1],
 [0,5,0]]

Constraints

n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 10^5

Check if Matrix Is X-Matrix

Easy

Google

2 views

Topics:

Arrays

Problem

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.

Examples

For example, the grid below is an X-Matrix, so return true

[[2,0,0,1],
 [0,3,1,0],
 [0,5,2,0],
 [4,0,0,2]]

In the grid below is not an X-Matrix, return false

[[5,7,0],
 [0,3,1],
 [0,5,0]]

Constraints

n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 10^5

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 True

Big(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 True

Big(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.

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

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 True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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 True

Big(O) Analysis

Time Complexity

Space Complexity

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.