Check if Matrix Is X-Matrix - Practice Coding Problems

Check if Matrix Is X-Matrix - Problem

Array Matrix Easy

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.

Input & Output

Example 1 — Valid X-Matrix

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

› Output: true

💡 Note: All diagonal elements (2,3,1,2,4,1,2,2) are non-zero, and all non-diagonal elements are 0. This forms a valid X-Matrix pattern.

Example 2 — Invalid X-Matrix

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

› Output: false

💡 Note: Element at position (0,1) has value 7 which is non-zero, but it's not on any diagonal. Non-diagonal elements must be 0 in an X-Matrix.

Example 3 — Zero on Diagonal

$ Input: grid = [[5,0,5],[0,0,1],[5,1,5]]

› Output: false

💡 Note: The center element at (1,1) is 0, but it's on the main diagonal. Diagonal elements must be non-zero in an X-Matrix.

Constraints

n == grid.length == grid[i].length
3 ≤ n ≤ 100
-10⁵ ≤ grid[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

4×4 matrix with values to be checked

Identify Diagonals

Main diagonal (i==j) and anti-diagonal (i+j==n-1)

Validate Pattern

Check if diagonals are non-zero and others are zero

Key Takeaway

🎯 Key Insight: Check diagonal positions using i==j (main) and i+j==n-1 (anti-diagonal) conditions

Asked in

a Amazon 15 M Microsoft 8

The key insight is identifying diagonal positions: main diagonal where i==j and anti-diagonal where i+j==n-1. Check that diagonal cells are non-zero and non-diagonal cells are zero. Best approach uses single pass with early return. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass with Early Return	O(n²)	O(1)	Check conditions in one pass and return false immediately when violation found
Brute Force - Check Every Cell	O(n²)	O(1)	Iterate through every cell and check if it satisfies X-Matrix conditions

Single Pass with Early Return — Algorithm Steps

Iterate through matrix cells
Return false immediately when finding a violation
Return true only if all cells pass the check

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cells

Start checking cells row by row

Early Exit

Return false immediately on first violation

Result

Saves time by not checking remaining cells

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int** grid, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // Check if current cell is on main diagonal or anti-diagonal
            bool isDiagonal = (i == j) || (i + j == n - 1);
            
            if (isDiagonal && grid[i][j] == 0) {
                return false; // Early return
            } else if (!isDiagonal && grid[i][j] != 0) {
                return false; // Early return
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for square matrix
    int n = 0;
    char* temp = line;
    while (*temp) {
        if (*temp == '[' && *(temp + 1) != '[') n++;
        temp++;
    }
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse numbers
    char* ptr = line;
    int row = 0, col = 0;
    while (*ptr && row < n) {
        if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
            grid[row][col] = strtol(ptr, &ptr, 10);
            col++;
            if (col == n) {
                col = 0;
                row++;
            }
        } else {
            ptr++;
        }
    }
    
    bool result = solution(grid, n);
    printf(result ? "true\n" : "false\n");
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case (valid X-matrix), we check all n×n cells

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

542 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass with Early Return — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler