Problem Description

A Toeplitz matrix is a matrix where every diagonal from top-left to bottom-right contains the same elements. Given an m x n matrix, you need to determine if it's a Toeplitz matrix.

In other words, for a matrix to be Toeplitz, all elements along each diagonal must be identical. Each diagonal starts from either the first row or the first column and extends diagonally down-right until it reaches the matrix boundary.

For example:

• In a Toeplitz matrix, if you pick any element at position (i, j), it should be equal to the element at position (i-1, j-1) (if such position exists).
• This means each element must match its upper-left neighbor.

The solution checks this property by iterating through the matrix starting from position (1, 1) and comparing each element with its upper-left diagonal neighbor at position (i-1, j-1). If any element doesn't match its upper-left neighbor, the matrix is not Toeplitz and returns false. If all elements satisfy this condition, the matrix is Toeplitz and returns true.

The time complexity is O(m × n) where m is the number of rows and n is the number of columns, as we need to check each element once. The space complexity is O(1) as we only use a constant amount of extra space.

Intuition

The key insight is recognizing that we don't need to check entire diagonals explicitly. Instead, we can leverage a simple property: if every element matches its upper-left neighbor, then all elements along each diagonal must be the same.

Think about it this way - if we follow any diagonal from top-left to bottom-right, each element on that diagonal can be viewed as the "next" element of the one above and to its left. If matrix[i][j] == matrix[i-1][j-1] for all valid positions, then by transitivity, all elements along the same diagonal must be equal.

For example, consider a diagonal passing through positions (0,2), (1,3), (2,4). If:

• matrix[1][3] == matrix[0][2]
• matrix[2][4] == matrix[1][3]

Then by transitivity: matrix[2][4] == matrix[1][3] == matrix[0][2], meaning the entire diagonal has the same value.

This observation simplifies our approach dramatically - instead of tracking and checking each diagonal separately, we just need a single pass through the matrix checking if each element (except those in the first row and first column) equals its upper-left neighbor. The elements in the first row and first column don't have upper-left neighbors, so they serve as the "starting points" for their respective diagonals.

This local check at each position is sufficient to guarantee the global property of the Toeplitz matrix, making the solution both elegant and efficient.

Solution Approach

The implementation uses a single traversal approach to check if the matrix is Toeplitz. Here's how the algorithm works:

1. Get matrix dimensions: First, we extract the number of rows m and columns n from the matrix.

   m, n = len(matrix), len(matrix[0])

2. Iterate through the matrix: We start our iteration from position (1, 1) instead of (0, 0). This is because elements in the first row and first column don't have upper-left neighbors to compare with.

   for i in range(1, m):
       for j in range(1, n):

3. Check the Toeplitz property: For each element at position (i, j), we compare it with its upper-left neighbor at position (i-1, j-1). If they're not equal, the matrix violates the Toeplitz property, and we immediately return False.

   if matrix[i][j] != matrix[i - 1][j - 1]:
       return False

4. Return the result: If we complete the entire traversal without finding any mismatches, all elements satisfy the Toeplitz property, so we return True.

   return True

The algorithm efficiently checks each element exactly once (except for the first row and column elements which are only used for comparison). The early return optimization means we stop as soon as we find the first violation, making the algorithm efficient for non-Toeplitz matrices.

This approach avoids the need to explicitly track or store diagonal values, using only the relative positioning of elements to verify the Toeplitz property throughout the entire matrix.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the algorithm works.

Consider this 3×4 matrix:

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

Step 1: Initialize dimensions

• m = 3 (rows), n = 4 (columns)

Step 2: Start checking from position (1,1)

We skip row 0 and column 0 since those elements don't have upper-left neighbors.

Iteration 1: Position (1,1)

• Current element: matrix[1][1] = 1
• Upper-left neighbor: matrix[0][0] = 1
• Comparison: 1 == 1 ✓ (Continue)

Iteration 2: Position (1,2)

• Current element: matrix[1][2] = 2
• Upper-left neighbor: matrix[0][1] = 2
• Comparison: 2 == 2 ✓ (Continue)

Iteration 3: Position (1,3)

• Current element: matrix[1][3] = 3
• Upper-left neighbor: matrix[0][2] = 3
• Comparison: 3 == 3 ✓ (Continue)

Iteration 4: Position (2,1)

• Current element: matrix[2][1] = 5
• Upper-left neighbor: matrix[1][0] = 5
• Comparison: 5 == 5 ✓ (Continue)

Iteration 5: Position (2,2)

• Current element: matrix[2][2] = 1
• Upper-left neighbor: matrix[1][1] = 1
• Comparison: 1 == 1 ✓ (Continue)

Iteration 6: Position (2,3)

• Current element: matrix[2][3] = 2
• Upper-left neighbor: matrix[1][2] = 2
• Comparison: 2 == 2 ✓ (Continue)

Result: All checks passed, return True. The matrix is Toeplitz!

Notice how the diagonals are preserved:

• Diagonal containing 1: positions (0,0) → (1,1) → (2,2)
• Diagonal containing 2: positions (0,1) → (1,2) → (2,3)
• Diagonal containing 3: positions (0,2) → (1,3)
• And so on...

Counter-example: If we had matrix[2][2] = 7 instead of 1, the algorithm would detect this at iteration 5 when comparing 7 != 1 and immediately return False.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the matrix. This is because the algorithm uses two nested loops - the outer loop iterates through rows from index 1 to m-1, and the inner loop iterates through columns from index 1 to n-1. Each cell (except those in the first row and first column) is visited exactly once to check if it equals its diagonal predecessor at position [i-1][j-1].

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables m, n, i, and j, regardless of the input matrix size. The algorithm performs the Toeplitz matrix validation in-place without creating any additional data structures that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Check Empty or Single-Element Matrices

One common pitfall is not considering edge cases where the matrix might be empty or have only one row/column. While the provided solution handles these cases correctly (they would return True since there are no diagonal violations to check), developers might overthink and add unnecessary special case handling.

Why it's not a problem here: The loop naturally handles these cases:

• Empty matrix: The loops don't execute, returns True
• Single row or column: The loops don't execute, returns True

2. Index Out of Bounds When Checking All Elements

A frequent mistake is trying to check every element in the matrix, including those in the first row and first column:

# WRONG: This will cause IndexError
for row in range(rows):  # Starting from 0
    for col in range(cols):  # Starting from 0
        if matrix[row][col] != matrix[row - 1][col - 1]:  # row-1 can be -1!
            return False

Solution: Always start iteration from index (1, 1) as shown in the correct implementation, since elements at row 0 or column 0 don't have upper-left neighbors.

3. Checking the Wrong Diagonal Direction

Developers might mistakenly check the wrong diagonal relationship:

# WRONG: Checking bottom-right instead of top-left
if matrix[row][col] != matrix[row + 1][col + 1]:  # Wrong direction!
    return False

# WRONG: Checking top-right diagonal
if matrix[row][col] != matrix[row - 1][col + 1]:  # Wrong diagonal!
    return False

Solution: Remember that Toeplitz matrices have consistent elements along top-left to bottom-right diagonals. Always compare with matrix[row - 1][col - 1].

4. Inefficient Diagonal Tracking

Some developers might try to explicitly track each diagonal using extra data structures:

# INEFFICIENT: Using dictionary to store diagonal values
diagonals = {}
for row in range(rows):
    for col in range(cols):
        diagonal_id = row - col
        if diagonal_id in diagonals:
            if diagonals[diagonal_id] != matrix[row][col]:
                return False
        else:
            diagonals[diagonal_id] = matrix[row][col]

Solution: The simple neighbor comparison approach is more efficient with O(1) space complexity instead of O(m+n) for storing diagonal values.

5. Off-by-One Errors in Loop Boundaries

Using incorrect loop boundaries can either miss checking elements or cause index errors:

# WRONG: Missing the last row/column
for row in range(1, rows - 1):  # Stops too early!
    for col in range(1, cols - 1):  # Stops too early!

# WRONG: Going beyond matrix boundaries
for row in range(1, rows + 1):  # Goes too far!
    for col in range(1, cols + 1):  # Goes too far!

Solution: Use range(1, rows) and range(1, cols) to correctly iterate through all valid positions that have upper-left neighbors.