2319. Check if Matrix Is X-Matrix


Problem Description

The problem requires us to determine if a given square matrix can be classified as an X-Matrix. A square matrix can be considered an X-Matrix if it meets two conditions:

  1. All elements on both its main diagonal (from top-left to bottom-right) and its anti-diagonal (from top-right to bottom-left) must be non-zero.
  2. All other elements, which are not part of the diagonals, must be zero.

Given an input matrix named grid, which is represented as a 2D integer array of size n x n, our task is to return true if grid is an X-Matrix, and false otherwise.

Intuition

To solve this problem, we can iterate over each element of the matrix and verify it against the two conditions provided for an X-Matrix. We can follow these steps:

  1. Loop through each element in the matrix using a nested loop, where i is the index for rows, and j is the index for columns.
  2. Check if the current element (grid[i][j]) belongs to either the main diagonal or the anti-diagonal. This is true when i == j (main diagonal) or i + j == len(grid) - 1 (anti-diagonal).
  3. If the current element belongs to one of the two diagonals, check if it is non-zero. If it is zero, we can immediately return false, as it violates the first condition for an X-Matrix.
  4. If the current element does not belong to a diagonal, check if it is zero. If it isn't, return false since this violates the second condition.
  5. If none of these violations occur during the traversal, return true, as the matrix satisfies both conditions for an X-Matrix.

The solution approach directly translates this intuition into a pair of nested loops that inspect each element based on its position in the matrix. By ensuring that diagonal elements are non-zero and others are zero, the solution effectively determines the X-Matrix validity.

Solution Approach

The solution leverages a straightforward approach without using any additional data structures or complex patterns. It is purely based on element-wise inspection of the matrix. Here is how the code implements the strategy to check if the given matrix is an X-Matrix:

  1. We use two nested loops to traverse each element of grid, where the outer loop uses the variable i to iterate over rows, and the inner loop uses j to iterate over columns. This allows us to check each element (denoted as v).

  2. The main diagonal is where the row index is equal to the column index (i == j). The anti-diagonal can be identified in a square matrix of size n by the condition where the sum of the row index and column index equals n - 1 (i + j == len(grid) - 1).

  3. Inside the loop, we check if the element belongs to either the main or anti-diagonal by evaluating the above two conditions. If the current element is part of a diagonal, we verify if it's non-zero. If a zero is found on any diagonal, the function immediately returns false, as it contradicts the first rule of an X-Matrix.

  4. If the current element does not lie on a diagonal, it must be zero to fulfill the second condition of an X-Matrix. Thus, any non-zero value encountered in this case leads to a return value of false.

  5. If the loop concludes without finding any violations of the X-Matrix rules, it means all diagonals contain non-zero values and all other elements are zero. Thus the function returns true, confirming that the grid is an X-Matrix.

The implementation is efficient, with a time complexity of O(n^2), which is required to check every element, and space complexity of O(1), as no additional space is required beyond input and variables for iteration.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Consider a small 3x3 matrix (grid):

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

We need to determine if this matrix is an X-Matrix according to the rules provided.

  1. To check if each diagonal element is non-zero, we start with the first element on the main diagonal, grid[0][0], which is 2. It's non-zero, so we proceed.
  2. Checking the next main diagonal element, grid[1][1], we find a 4. It's also non-zero, so we continue.
  3. Checking the last element on the main diagonal, grid[2][2], we see a 5. It's non-zero as well, hence the main diagonal condition is satisfied.
  4. Next, we move to the anti-diagonal. We start with grid[0][2], which is 3, and then grid[1][1] (which we've already checked), and finally grid[2][0], which is 1. All these elements are also non-zero, satisfying the anti-diagonal condition.
  5. None of the diagonal elements are zero, so the first condition for an X-Matrix is met.
  6. Now we check all other elements, which should all be zero. We review grid[0][1], grid[1][0], grid[1][2], and grid[2][1]. They are all zero, as required.
  7. Since we have verified that all diagonal elements are non-zero and all other elements are zero, we confirm that the matrix is an X-Matrix. Therefore, the function would return true.

In this example, we've walked through the matrix and checked both conditions specified for an X-Matrix. The matrix given fulfills both conditions, so it is indeed an X-Matrix.

Solution Implementation

1class Solution:
2    def checkXMatrix(self, grid: List[List[int]]) -> bool:
3        n = len(grid)  # The dimension of the square grid
4        # Iterate through each element of the grid
5        for i in range(n):
6            for j in range(n):
7                # Check if we are on the main or secondary diagonal
8                if i == j or i + j == n - 1:
9                    # If the value on the diagonal is 0, the condition fails
10                    if grid[i][j] == 0:
11                        return False
12                else:
13                    # If the value is not on the diagonal and is not 0, the condition fails
14                    if grid[i][j] != 0:
15                        return False
16        # If all conditions are satisfied, return True
17        return True
18
1class Solution {
2
3    // Function to check if the given grid forms an X-Matrix
4    public boolean checkXMatrix(int[][] grid) {
5        // Get the length of the grid (since it's an N x N matrix)
6        int n = grid.length;
7      
8        // Loop through each element of the grid
9        for (int i = 0; i < n; ++i) {
10            for (int j = 0; j < n; ++j) {
11                // Check the diagonal and anti-diagonal 
12                if (i == j || i + j == n - 1) {
13                    // On the diagonals, all elements should be non-zero
14                    // If a zero is found, the grid is not an X-Matrix
15                    if (grid[i][j] == 0) {
16                        return false;
17                    }
18                } else {
19                    // For all other positions (off the diagonals), elements should be zero
20                    // If a non-zero number is found, the grid is not an X-Matrix
21                    if (grid[i][j] != 0) {
22                        return false;
23                    }
24                }
25            }
26        }
27      
28        // If all conditions are met, then it's an X-Matrix
29        return true;
30    }
31}
32
1class Solution {
2public:
3    // Function to check if a given grid forms an X-Matrix
4    bool checkXMatrix(vector<vector<int>>& grid) {
5        // Get the size of the grid
6        int n = grid.size();
7      
8        // Iterate over each element in the grid
9        for (int i = 0; i < n; ++i) {
10            for (int j = 0; j < n; ++j) {
11                // Check the diagonals: primary (i == j) and secondary (i + j == n - 1)
12                if (i == j || i + j == n - 1) {
13                    // If an element on the diagonal is zero, the grid does not form an X-Matrix
14                    if (grid[i][j] == 0) {
15                        return false;
16                    }
17                }
18                // Check the elements that are not on the diagonals
19                else {
20                    // If an off-diagonal element is not zero, the grid does not form an X-Matrix
21                    if (grid[i][j] != 0) {
22                        return false;
23                    }
24                }
25            }
26        }
27        // Return true if all diagonal elements are non-zero and all off-diagonal elements are zero
28        return true;
29    }
30};
31
1// Function to check if a given 2D grid forms an X-Matrix.
2// An X-Matrix has non-zero integers on both its diagonals,
3// and zeros on all other positions.
4function checkXMatrix(grid: number[][]): boolean {
5    // Get the size of the grid.
6    const size = grid.length;
7
8    // Loop over each element in the grid.
9    for (let row = 0; row < size; ++row) {
10        for (let col = 0; col < size; ++col) {
11            // Check the main diagonal and anti-diagonal elements
12            if (row === col || row + col === size - 1) {
13                // If any diagonal element is 0, return false.
14                if (grid[row][col] === 0) {
15                    return false;
16                }
17            } else {
18                // If any off-diagonal element is non-zero, return false.
19                if (grid[row][col] !== 0) {
20                    return false;
21                }
22            }
23        }
24    }
25
26    // If no rule is violated, return true.
27    return true;
28}
29

Time and Space Complexity

The given code snippet is designed to check whether a given square 2D grid is an 'X-Matrix'. An 'X-Matrix' has non-zero elements on its diagonals and zero elements elsewhere.

Time Complexity

To determine the time complexity, we look at the number of operations relative to the input size. The code iterates over every element in the N x N grid exactly once, performing a constant amount of work for each element by checking if it's on the diagonal or anti-diagonal and then validating the value. Therefore, the time complexity is O(N^2), where N is the length of the grid's side.

Space Complexity

The solution only uses a fixed number of variables (i, j, v) and does not allocate any additional space that grows with the input size. Hence, the space complexity is O(1) as it does not depend on the size of the input grid.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More