algoadvance

Leetcode 2319. Check if Matrix Is X

Problem Statement

You are given a 2D integer array grid of size n x n representing a square matrix. An X-Matrix is a matrix where all the elements in the diagonals of the matrix are non-zero and all other elements are 0.

Given this definition, an element grid[i][j] is part of the diagonals if either:

• i == j (it is on the primary diagonal),
• i + j == n - 1 (it is on the secondary diagonal).

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

Example 2:

Input: grid = [[5,7,0],[0,3,1],[0,5,0]]
Output: false
Explanation: One of the elements in the diagonals is zero.

Clarifying Questions

1. What is the size of the matrix grid?
   • The input matrix is square and of size n x n.
2. What kind of values does the matrix contain?
   • The matrix contains integer values, which can be positive, negative, or zero.
3. Is there a constraint on the value of n?
   • Typical constraints from LeetCode problems will ensure that 1 <= n <= 100.

Strategy

1. Traverse the matrix and check each element.
2. For each element grid[i][j]:
   • If it is on the primary or secondary diagonal (i == j or i + j == n - 1), it should be non-zero.
   • If it is not on either diagonal, it should be zero.
3. If all elements meet the requirements, the matrix is an X-Matrix; otherwise, it is not.

Code

public class Solution {
    public boolean 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) {
                    // Element is on the diagonal
                    if (grid[i][j] == 0) {
                        return false;
                    }
                } else {
                    // Element is not on the diagonal
                    if (grid[i][j] != 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Time Complexity

• Time Complexity: O(n^2) - We need to iterate through all the elements of the matrix exactly once to perform the checks.
• Space Complexity: O(1) - We are using a constant amount of extra space.

This approach should efficiently determine if the matrix grid is an X-Matrix based on the defined criteria.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?