Toeplitz Matrix - Practice Coding Problems

Toeplitz Matrix - Problem

Array Matrix Easy

Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

In other words, a matrix is Toeplitz if matrix[i][j] == matrix[i+1][j+1] for all valid i and j.

Input & Output

Example 1 — Valid Toeplitz Matrix

$ Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]

› Output: true

💡 Note: Every diagonal from top-left to bottom-right has the same elements: diagonal [1,1,1], diagonal [2,2,2], diagonal [3,3], diagonal [4], diagonal [5,5], diagonal [9]

Example 2 — Invalid Toeplitz Matrix

$ Input: matrix = [[1,2],[2,2]]

› Output: false

💡 Note: The diagonal from top-left has elements [1,2] which are not all the same, so it's not a Toeplitz matrix

Example 3 — Single Element Matrix

$ Input: matrix = [[1]]

› Output: true

💡 Note: A single element matrix is always Toeplitz since there are no diagonals to violate the property

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 20
0 ≤ matrix[i][j] ≤ 99

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x4 matrix with elements to be checked

Diagonal Check

Verify each diagonal has same elements

Result

Return true if all diagonals are uniform

Key Takeaway

🎯 Key Insight: A matrix is Toeplitz if matrix[i][j] == matrix[i+1][j+1] for all valid positions

Asked in

G Google 15 f Facebook 12

The key insight is that a Toeplitz matrix requires every diagonal from top-left to bottom-right to have identical elements. The optimal approach compares each element directly with its diagonal neighbor at position (i+1, j+1) in a single pass. Time: O(m×n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Check All Diagonals	O(m×n)	O(m+n)	For each diagonal, collect all elements and verify they're identical
Single Pass Comparison	O(m×n)	O(1)	Compare each element directly with its diagonal neighbor below-right

Check All Diagonals — Algorithm Steps

Identify all diagonal starting positions
For each diagonal, collect all elements
Check if all elements in diagonal are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Diagonals

Start from first row and first column positions

Collect Elements

Traverse each diagonal gathering all elements

Verify Uniformity

Check if all elements in each diagonal are the same

Code -

solution.c — C

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

bool solution(int** matrix, int matrixSize, int* matrixColSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        return true;
    }
    
    int m = matrixSize;
    int n = matrixColSize[0];
    
    // Check diagonals starting from first row
    for (int col = 0; col < n; col++) {
        int diagonal[1000];
        int diagSize = 0;
        int i = 0, j = col;
        while (i < m && j < n) {
            diagonal[diagSize++] = matrix[i][j];
            i++;
            j++;
        }
        
        // Check if all elements in diagonal are same
        for (int k = 1; k < diagSize; k++) {
            if (diagonal[k] != diagonal[0]) {
                return false;
            }
        }
    }
    
    // Check diagonals starting from first column (skip [0,0])
    for (int row = 1; row < m; row++) {
        int diagonal[1000];
        int diagSize = 0;
        int i = row, j = 0;
        while (i < m && j < n) {
            diagonal[diagSize++] = matrix[i][j];
            i++;
            j++;
        }
        
        // Check if all elements in diagonal are same
        for (int k = 1; k < diagSize; k++) {
            if (diagonal[k] != diagonal[0]) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple matrix parsing
    int matrix[300][300];
    int* matrixPtrs[300];
    int matrixColSize[300];
    int matrixSize = 0;
    
    // Basic JSON parsing for matrix
    char* ptr = line + 1; // Skip first '['
    int row = 0;
    
    while (*ptr && row < 300) {
        if (*ptr == '[') {
            ptr++;
            int col = 0;
            while (*ptr && *ptr != ']' && col < 300) {
                if (*ptr == '-' || (*ptr >= '0' && *ptr <= '9')) {
                    matrix[row][col] = atoi(ptr);
                    col++;
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                    if (*ptr == ',') ptr++;
                } else {
                    ptr++;
                }
            }
            matrixPtrs[row] = matrix[row];
            matrixColSize[row] = col;
            row++;
            if (*ptr == ']') ptr++;
            if (*ptr == ',') ptr++;
        } else {
            ptr++;
        }
    }
    matrixSize = row;
    
    bool result = solution(matrixPtrs, matrixSize, matrixColSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Visit each element once to collect diagonals, then check each diagonal

✓ Linear Growth

Space Complexity

O(m+n)

Store elements of longest diagonal which can be min(m,n) elements

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.1K 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

Check All Diagonals — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler