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:
- 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.
- 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:
- Loop through each element in the matrix using a nested loop, where
i
is the index for rows, andj
is the index for columns. - Check if the current element (
grid[i][j]
) belongs to either the main diagonal or the anti-diagonal. This is true wheni == j
(main diagonal) ori + j == len(grid) - 1
(anti-diagonal). - 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. - 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. - 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:
-
We use two nested loops to traverse each element of
grid
, where the outer loop uses the variablei
to iterate over rows, and the inner loop usesj
to iterate over columns. This allows us to check each element (denoted asv
). -
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 sizen
by the condition where the sum of the row index and column index equalsn - 1
(i + j == len(grid) - 1
). -
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. -
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
. -
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 thegrid
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 EvaluatorExample 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.
- To check if each diagonal element is non-zero, we start with the first element on the main diagonal,
grid[0][0]
, which is2
. It's non-zero, so we proceed. - Checking the next main diagonal element,
grid[1][1]
, we find a4
. It's also non-zero, so we continue. - Checking the last element on the main diagonal,
grid[2][2]
, we see a5
. It's non-zero as well, hence the main diagonal condition is satisfied. - Next, we move to the anti-diagonal. We start with
grid[0][2]
, which is3
, and thengrid[1][1]
(which we've already checked), and finallygrid[2][0]
, which is1
. All these elements are also non-zero, satisfying the anti-diagonal condition. - None of the diagonal elements are zero, so the first condition for an X-Matrix is met.
- Now we check all other elements, which should all be zero. We review
grid[0][1]
,grid[1][0]
,grid[1][2]
, andgrid[2][1]
. They are all zero, as required. - 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.
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!