Check if Matrix Is X-Matrix

EASY

Description

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].length
3 <= n <= 100
0 <= grid[i][j] <= 10⁵

Approaches

Checkout 2 different approaches to solve Check if Matrix Is X-Matrix. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Extra Space

This approach involves pre-calculating the coordinates of all diagonal and non-diagonal elements and storing them in separate data structures. It then iterates through these stored coordinates to check the matrix values against the X-Matrix conditions. While functionally correct, it's inefficient due to high memory usage.

Algorithm

Get the dimension n of the matrix.
Create two lists, diagonalCoords and nonDiagonalCoords, to store coordinates.
Iterate from i = 0 to n-1 and j = 0 to n-1:
- If i == j or i + j == n - 1, add the coordinate (i, j) to diagonalCoords.
- Otherwise, add (i, j) to nonDiagonalCoords.
Iterate through each coordinate (r, c) in diagonalCoords:
- If grid[r][c] is 0, return false.
Iterate through each coordinate (r, c) in nonDiagonalCoords:
- If grid[r][c] is not 0, return false.
If all checks pass, return true.

The core idea is to separate the identification of element positions from the validation of their values. We first iterate through all possible indices (i, j) of the n x n matrix. For each index, we determine if it lies on the main diagonal (i == j) or the anti-diagonal (i + j == n - 1). We maintain two lists of coordinates: one for diagonal elements and one for non-diagonal elements. After populating these lists, we perform two separate checks:

Iterate through the list of diagonal coordinates and verify that every corresponding element in the grid is non-zero. If we find a zero, we immediately return false.
Iterate through the list of non-diagonal coordinates and verify that every corresponding element in the grid is zero. If we find a non-zero value, we return false. If both checks pass completely, it means the matrix satisfies the X-Matrix properties, and we return true.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        List<int[]> diagonalCoords = new ArrayList<>();
        List<int[]> nonDiagonalCoords = new ArrayList<>();

        // Step 1: Populate coordinate lists
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i + j == n - 1) {
                    diagonalCoords.add(new int[]{i, j});
                } else {
                    nonDiagonalCoords.add(new int[]{i, j});
                }
            }
        }

        // Step 2: Check diagonal elements
        for (int[] coord : diagonalCoords) {
            if (grid[coord[0]][coord[1]] == 0) {
                return false;
            }
        }

        // Step 3: Check non-diagonal elements
        for (int[] coord : nonDiagonalCoords) {
            if (grid[coord[0]][coord[1]] != 0) {
                return false;
            }
        }

        return true;
    }
}

Complexity Analysis

Time Complexity: O(n^2). The first nested loop to populate the lists takes O(n^2). The subsequent loops iterate through O(n) and O(n^2) elements respectively. The total time is dominated by O(n^2).Space Complexity: O(n^2). We store coordinates for all `n^2` elements in the matrix across two lists.

Pros and Cons

Pros:

Separation of concerns: The logic for identifying positions is separate from the logic for validating values.
Easy to understand and debug due to the explicit separation of steps.

Cons:

Highly inefficient in terms of space, using O(n^2) extra memory.
Unnecessary overhead of creating and managing lists of coordinates.
Multiple passes over the data (conceptually), which is less efficient than a single pass.

Code Solutions

Checking out 4 solutions in different languages for Check if Matrix Is X-Matrix. Click on different languages to view the code.

public class Solution {
    public bool CheckXMatrix(int[][] grid) {
        int n = grid.Length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || i + j == n - 1) {
                    if (grid[i][j] == 0) {
                        return false;
                    }
                } else if (grid[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

Video Solution

Watch the video walkthrough for Check if Matrix Is X-Matrix

Data Structures:

ArrayMatrix