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