algoadvance

Leetcode 2319. Check if Matrix Is X

Problem Statement

Given a square matrix grid, return true if the matrix is an X-Matrix. Otherwise, return false.

An X-Matrix has the following properties:

  1. All the elements in the diagonals of the matrix are non-zero.
  2. All other elements are zeros.

For example:

Input: grid = [[2,0,0,1],
               [0,3,1,0],
               [0,5,2,0],
               [4,0,0,2]]
Output: true

Input: grid = [[5,7,0],
               [0,3,1],
               [1,0,5]]
Output: false

Clarifying Questions

  1. What are the constraints on the size of the matrix grid?
  2. Can we assume that the input grid is always a square matrix (i.e., same number of rows and columns)?
  3. Are there any constraints on the values of the elements in the matrix?

Strategy

To determine if a given matrix is an X-Matrix, use the following steps:

  1. Iterate over each element in the matrix.
  2. Check if the element is on one of the diagonals:
    • Primary diagonal: i == j
    • Secondary diagonal: i + j == n - 1
  3. Confirm that diagonal elements are non-zero.
  4. Confirm that non-diagonal elements are zero.
  5. Return true if both conditions are satisfied for all elements, otherwise return false.

Code

#include <vector>

using namespace std;

class Solution {
public:
    bool checkXMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        
        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;
    }
};

Time Complexity

The time complexity of this solution is (O(n^2)) because we need to iterate through each element in the n x n matrix exactly once to check the conditions.

Explanation

  1. Primary Diagonal Check:
    • Positions where i == j are points on the primary diagonal.
  2. Secondary Diagonal Check:
    • Positions where i + j == n - 1 are points on the secondary diagonal.
  3. Validation:
    • For diagonal elements (i == j or i + j == n - 1), ensure they are non-zero.
    • For non-diagonal elements, ensure they are zero.

This approach ensures that every element is checked exactly once, leading to optimal performance.

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