#766

Easy

LeetCode Problem Workspace

Toeplitz Matrix

Determine if a given matrix is a Toeplitz matrix by checking diagonal consistency.

Problem Statement

You are given an m x n matrix. A matrix is considered Toeplitz if every diagonal from top-left to bottom-right has the same elements. Your task is to return true if the matrix is Toeplitz and false otherwise.

To determine if a matrix is Toeplitz, check every diagonal of the matrix. Specifically, for each element in the matrix, verify that it is equal to its top-left neighbor (if that neighbor exists).

Examples

Example 1

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

Output: true

In the above grid, the diagonals are: "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]". In each diagonal all elements are the same, so the answer is True.

Example 2

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

Output: false

The diagonal "[1, 2]" has different elements.

Constraints

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

Solution Approach

Iterate and Compare

Loop through the matrix, starting from the second row and column. For each element, compare it with the element diagonally above-left. If any mismatch is found, return false.

Optimized Check

For optimization, compare only the diagonals starting from the second row and column to minimize redundant checks. This reduces unnecessary comparisons.

Edge Case Handling

Handle edge cases such as matrices with a single row or column, where all diagonals automatically meet the condition. Also, consider the smallest matrices with just one element.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the matrix dimensions. A naive solution checks every element and compares it with its diagonal neighbor, leading to a time complexity of O(m*n). Optimizations may reduce this, but this is typically the expected case. The space complexity is O(1), as no additional space is required beyond the matrix itself.

What Interviewers Usually Probe

The candidate efficiently checks diagonals without redundant comparisons.
The candidate understands edge case handling and matrix traversal.
The candidate optimizes the solution when applicable, reducing unnecessary checks.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle matrices with a single row or column.
Overlooking the need for diagonal comparison from the second row and column.
Not optimizing for edge cases where the matrix size is small, such as 1x1 matrices.

Follow-up variants

Consider matrices of larger sizes, pushing the time complexity boundaries.
Solve this problem in a non-iterative manner, exploring matrix transformations.
Modify the problem to check for Toeplitz properties in other directions or shapes.

FAQ

What is a Toeplitz matrix?

A Toeplitz matrix is a matrix where every diagonal from top-left to bottom-right contains identical elements.

How do I determine if a matrix is Toeplitz?

To check if a matrix is Toeplitz, iterate through the matrix and compare each element to its top-left diagonal neighbor.

What happens if one diagonal doesn't match?

If any diagonal doesn't have identical elements, the matrix is not Toeplitz, and you should return false.

How does the 'Array plus Matrix' pattern relate to this problem?

This problem combines array traversal techniques with matrix handling, where diagonal checking mimics the 'Array' pattern in the context of a 2D matrix.

What are common mistakes when solving the Toeplitz matrix problem?

Common mistakes include not properly handling edge cases like single-row or single-column matrices, and missing efficient checks for diagonals starting from the second row and column.

terminal

Solution

Solution 1: Single Traversal

According to the problem description, the characteristic of a Toeplitz matrix is that each element is equal to the element in its upper left corner. Therefore, we only need to iterate through each element in the matrix and check if it is equal to the element in its upper left corner.

1

2

3

4

5

6

7

8

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] != matrix[i - 1][j - 1]:
                    return False
        return True

Continue Practicing

#773 sliding puzzle #778 swim in rising water #782 transform to chessboard