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:

  1. Iterate through each element matrix[i][j] (with i from 0 to m-2 and j from 0 to n-2).
  2. For each element, compare matrix[i][j] with matrix[i+1][j+1].
  3. 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:

  1. Initialize an empty dictionary.
  2. 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.
  3. 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]
]
  1. 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.
  2. Conclusion:
    Since all elements match their bottom-right neighbors, the matrix is Toeplitz.

Code Implementation

Python Code

Python3
Python3

. . . .

Java Code

Java
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.

TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.