algoadvance

Clarifying Questions

1. What is an X-Matrix?
   • An X-Matrix is a square matrix (n x n) where all the diagonal elements (both primary and secondary diagonals) are non-zero, and all other elements are zero.
2. Constraints:
   • What are the minimal and maximal sizes of the matrix?
   • Are there any specific value ranges for the elements within the matrix?
   • Will the matrix always be a square matrix?

Strategy

1. Identify Diagonal Positions:
   • Primary diagonal elements in a matrix are the ones where the row and column indices are the same (i.e., i == j).
   • Secondary diagonal elements are the ones where the sum of row and column indices equals n - 1 (i.e., i + j == n - 1).
2. Validation Checks:
   • Traverse through each element of the matrix.
   • Check if the element is on the primary or secondary diagonal:
     • If it is, ensure it is non-zero.
     • If it is not, ensure it is zero.
3. Early Termination:
   • As soon as an invalid condition (zero on diagonal or non-zero off diagonal) is found, return False.
4. Completion:
   • If all elements satisfy the conditions, return True.

Code

def checkXMatrix(grid):
    n = len(grid)  # The matrix is n x n

    for i in range(n):
        for j in range(n):
            if i == j or i + j == n - 1:
                # Primary diagonal or secondary diagonal element
                if grid[i][j] == 0:
                    return False
            else:
                # Non-diagonal element
                if grid[i][j] != 0:
                    return False
                    
    return True

Time Complexity

• Time Complexity: O(n^2), where n is the size of the grid (number of rows/columns). This is because we need to check each element in the n x n matrix exactly once.
• Space Complexity: O(1), as no additional space proportional to the input size is used. Only a constant amount of space is required for the indices and any temporary variables.

Example Use Case

# Sample test case
matrix = [
    [2, 0, 0, 1],
    [0, 3, 1, 0],
    [0, 5, 2, 0],
    [4, 0, 0, 2]
]

print(checkXMatrix(matrix))  # Output should be True as it is an X-Matrix

matrix = [
    [2, 0, 4, 1],
    [0, 3, 0, 0],
    [0, 0, 2, 0],
    [4, 0, 0, 2]
]

print(checkXMatrix(matrix))  # Output should be False as it is not an X-Matrix

This logic should help you implement the solution to check if a given matrix is an X-Matrix. If you have any further questions or need additional test cases, feel free to ask!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?