766. Toeplitz Matrix - Detailed Explanation

Problem Statement

Description:
A matrix is called Toeplitz if every diagonal from top-left to bottom-right has the same element. In other words, for all valid indices, the element at position matrix[i][j] should be the same as the element at position matrix[i+1][j+1].

Constraints:

The number of rows and columns can vary.
The matrix may have dimensions such that one of them is 0 or 1.
The values in the matrix can be any integers.

Example 1:

Input:

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

Output: true
Explanation:
Every diagonal from top-left to bottom-right has the same element. For instance, the diagonal starting at matrix[0][0] (which is 1) continues with matrix[1][1] (1) and matrix[2][2] (1).

Example 2:

Input:
```
matrix = [
    [1, 2],
    [2, 2]
]
```
Output: false
Explanation:
The diagonal starting at matrix[0][0] (which is 1) continues with matrix[1][1] (2), so the condition is not met.

Hints

Hint 1: Focus on the property that defines a Toeplitz matrix: each element (except those in the last row or column) should match its bottom-right neighbor.
Hint 2: Think about how you can iterate over the matrix in one pass and compare each element with matrix[i+1][j+1]. Be mindful of the boundaries.
Hint 3: Consider an alternative approach using a hash map (dictionary) where the key is the difference i - j (which uniquely identifies each diagonal). The first element in a diagonal can be used as a reference for all other elements in that diagonal.

Approaches

Direct Comparison (One-Pass Check)

Idea:
Loop through the matrix (except for the last row and column) and check if the current element is equal to the element diagonally down-right.

Steps:

Iterate through each element matrix[i][j] (with i from 0 to m-2 and j from 0 to n-2).
For each element, compare matrix[i][j] with matrix[i+1][j+1].
If any comparison fails, return false. If all pass, return true.

Complexity:

Time Complexity: O(m * n) – each element is visited once.
Space Complexity: O(1) – constant extra space.

Dictionary-Based Grouping by Diagonals

Idea:
Use a dictionary where each key is i - j. For each element, check if its value matches the stored value for that diagonal (if any).

Steps:

Initialize an empty dictionary.
Loop through the matrix. For each element at (i, j):
- If the key i - j is not in the dictionary, store the element.
- If the key exists, check if the current element is equal to the stored element.
Return false if a mismatch is found; otherwise, return true.

Complexity:

Time Complexity: O(m * n)
Space Complexity: O(m + n) in the worst-case scenario when there are many different diagonals.

Detailed Walkthrough (Using the Direct Comparison Approach)

Consider the matrix:

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

Start Iteration:
- Row 0:
  - Compare matrix[0][0] (1) with matrix[1][1] (1) → They match.
  - Compare matrix[0][1] (2) with matrix[1][2] (2) → They match.
  - Compare matrix[0][2] (3) with matrix[1][3] (3) → They match.
- Row 1:
  - Compare matrix[1][0] (5) with matrix[2][1] (5) → They match.
  - Compare matrix[1][1] (1) with matrix[2][2] (1) → They match.
  - Compare matrix[1][2] (2) with matrix[2][3] (2) → They match.
Conclusion:
Since all elements match their bottom-right neighbors, the matrix is Toeplitz.

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- Both approaches run in O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity:
- Direct Comparison Approach: O(1) – no additional space is used.
- Dictionary-Based Approach: O(m + n) in the worst-case scenario (for storing keys corresponding to each diagonal).

Additional Sections

Common Mistakes

Not Handling Boundaries Properly:
It is common to accidentally index out of bounds when comparing matrix[i+1][j+1] if you don’t limit your loop to rows-1 and cols-1.
Overcomplicating the Logic:
The problem can be solved with a simple pairwise comparison. Introducing extra data structures unnecessarily can make the solution less efficient.

Edge Cases

Single Row or Single Column:
A matrix with only one row or one column is always Toeplitz because there are no diagonals to compare.
Empty Matrix:
Although not usually provided in the constraints, if an empty matrix is given, you may need to define what should be returned.

Variations:
- Checking for “Reverse Toeplitz” matrices, where each diagonal from top-right to bottom-left has the same element.
- Determining if a matrix has other specific diagonal properties.

Conclusion

In the Toeplitz Matrix problem, the key observation is that each element (except those on the boundaries) must equal its bottom-right neighbor. We presented a straightforward one-pass approach that directly compares adjacent diagonal elements, as well as an alternative dictionary-based approach that groups elements by their diagonal identifier (i - j). Both methods are efficient with O(m * n) time complexity, but the direct comparison method is simpler and uses constant space.