Domain 1EasyCORE

Toeplitz Matrix

The problem requires determining whether a given `m x n` matrix is Toeplitz. A matrix is considered Toeplitz if every diagonal from the top-left to the bottom-right contains the same elements. The input is a 2D array (matrix), and the output should be a boolean value (`true` or `false`).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

766. Toeplitz Matrix

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 65.9%


Problem Breakdown

The problem requires determining whether a given m x n matrix is Toeplitz. A matrix is considered Toeplitz if every diagonal from the top-left to the bottom-right contains the same elements. The input is a 2D array (matrix), and the output should be a boolean value (true or false).

Inputs:

  • A 2D array matrix of integers.

Outputs:

  • Boolean value indicating whether the matrix is Toeplitz.

Implicit Constraints/Edge Cases:

  • The matrix can be as small as 1x1.
  • The matrix elements are non-negative integers (0 to 99).
  • The matrix dimensions are limited to m, n <= 20.

Intuition

The brute-force approach would involve checking each diagonal individually. For each element in the first row and the first column, we could traverse down the diagonal and ensure all elements are equal. However, this approach is inefficient with a time complexity of O(m * n^2) because for each starting point, we potentially traverse the entire length of the matrix.

A more efficient approach involves recognizing that each element in the matrix should be equal to the element diagonally above-left of it (if such an element exists). This insight allows us to check only adjacent elements rather than traversing entire diagonals, reducing the time complexity to O(m * n).

Approach

  1. Iterate through each element in the matrix starting from the second row and the second column.
  2. For each element matrix[i][j], compare it with the element diagonally above-left of it: matrix[i-1][j-1].
  3. If any pair of elements does not match, return false.
  4. If all pairs match, return true.

This approach leverages the fact that if a matrix is Toeplitz, then each element should be equal to its diagonal neighbor above-left.

Complexity Analysis

  • Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. We iterate through each element once.
  • Space Complexity: O(1). We only use a constant amount of extra space for variables.

Solution

def isToeplitzMatrix(matrix):
    # Iterate through the matrix starting from the second row and second column
    for i in range(1, len(matrix)):
        for j in range(1, len(matrix[0])):
            # Check if the current element is equal to the element diagonally above-left
            if matrix[i][j] != matrix[i-1][j-1]:
                return False
    return True

Edge Cases Handled

  • Single-element matrix: A 1x1 matrix is trivially Toeplitz.
  • All elements identical: If all elements in the matrix are the same, it is Toeplitz.
  • Non-Toeplitz diagonals: Any diagonal with differing elements will result in a false return value.

This solution efficiently checks the Toeplitz condition by leveraging the properties of diagonals in a matrix, ensuring optimal performance even within the given constraints.