Check if Matrix Is X-Matrix

Easy
297.

Check if Matrix Is X-Matrix

Check if Matrix Is X-Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.

A square matrix is an X-Matrix when both hold:

  1. Every element on one of the two main diagonals is non-zero.
  2. Every other element is zero.

Given a square matrix grid, return true if it is an X-Matrix.

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
The 7 sits off both diagonals but is non-zero.

Example 3

Input
grid = [[1]]
Output
true

Constraints

  • 1 <= grid.length <= 8
  • grid[i].length == grid.length
  • 0 <= grid[i][j] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var checkXMatrix = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if Matrix Is X-Matrix — Solution in Python, Java & C++

Check if Matrix Is X-Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Check if Matrix Is X-Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A square matrix is an X-Matrix when both hold:

  1. Every element on one of the two main diagonals is non-zero.
  2. Every other element is zero.

Given a square matrix grid, return true if it is an X-Matrix.

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: The 7 sits off both diagonals but is non-zero.

Example 3

Input: grid = [[1]]
Output: true

Constraints

  • 1 <= grid.length <= 8
  • grid[i].length == grid.length
  • 0 <= grid[i][j] <= 100000

Hints for Check if Matrix Is X-Matrix

  1. Hint 1

    A cell (r, c) is on a diagonal exactly when r == c or r + c == n - 1.

  2. Hint 2

    One pass over every cell checks both rules with a single branch.

  3. Hint 3

    The centre of an odd-sized matrix satisfies both conditions at once — it is still just a diagonal cell.

How to solve Check if Matrix Is X-Matrix

A cell is on a diagonal iff r == c or r + c == n - 1; diagonal cells must be non-zero and every other cell must be zero.

Approach

  1. For each cell compute onDiagonal.
  2. Return false if a diagonal cell is 0 or a non-diagonal cell is non-zero.
  3. Return true.

Why it works

The two conditions partition the cells, so one pass with a single branch checks both rules.

Complexity

  • Time — O(n²)
  • Space — O(1)

Pitfalls

  • The centre of an odd-sized matrix satisfies both diagonal tests; it is still just a diagonal cell.

Reference solution

Python

def checkXMatrix(grid) -> bool:
    n = len(grid)
    for r in range(n):
        for c in range(n):
            on_diagonal = r == c or r + c == n - 1
            if on_diagonal and grid[r][c] == 0:
                return False
            if not on_diagonal and grid[r][c] != 0:
                return False
    return True

Java

public static boolean checkXMatrix(int[][] grid) {
    int n = grid.length;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            boolean onDiagonal = r == c || r + c == n - 1;
            if (onDiagonal && grid[r][c] == 0) return false;
            if (!onDiagonal && grid[r][c] != 0) return false;
        }
    }
    return true;
}

C++

bool checkXMatrix(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            bool onDiagonal = r == c || r + c == n - 1;
            if (onDiagonal && grid[r][c] == 0) return false;
            if (!onDiagonal && grid[r][c] != 0) return false;
        }
    }
    return true;
}

JavaScript

var checkXMatrix = function(grid) {
    const n = grid.length;
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            const onDiagonal = r === c || r + c === n - 1;
            if (onDiagonal && grid[r][c] === 0) return false;
            if (!onDiagonal && grid[r][c] !== 0) return false;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal