Difficulty: Easy | Acceptance: 69.70% | Paid: No Topics: Array, Matrix
Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
- Examples
- Constraints
- Approach 1: Diagonal Traversal
- Approach 2: Compare with Top-Left Neighbor
- Approach 3: Hash Map by Diagonal Index
Examples
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.
Example 2:
Input: matrix = [[1,2],[2,2]]
Output: false
Explanation:
The diagonal "[1, 2]" has different elements.
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 20
0 <= matrix[i][j] <= 99
Approach 1: Diagonal Traversal
Intuition Iterate through each diagonal starting from the first row and first column, checking if all elements on each diagonal are equal.
Steps
- Start from each element in the first row and first column
- For each starting position, traverse diagonally down-right
- Compare all elements on the diagonal with the first element
- Return false if any mismatch is found
class Solution:
def isToeplitzMatrix(self, matrix):
m, n = len(matrix), len(matrix[0])
# Check diagonals starting from first row
for col in range(n):
val = matrix[0][col]
row, c = 1, col + 1
while row < m and c < n:
if matrix[row][c] != val:
return False
row += 1
c += 1
# Check diagonals starting from first column (excluding first element)
for row in range(1, m):
val = matrix[row][0]
r, col = row + 1, 1
while r < m and col < n:
if matrix[r][col] != val:
return False
r += 1
col += 1
return True
Complexity
- Time: O(m × n)
- Space: O(1)
- Notes: Visits each element at most once, but requires two separate loops for row and column starts
Approach 2: Compare with Top-Left Neighbor
Intuition For a Toeplitz matrix, each element must equal its top-left neighbor. Simply compare each element (except first row and column) with its diagonal predecessor.
Steps
- Iterate through the matrix starting from row 1 and column 1
- For each element, compare it with the element at (row-1, col-1)
- Return false if any mismatch is found
- Return true if all comparisons pass
class Solution:
def isToeplitzMatrix(self, matrix):
m, n = len(matrix), len(matrix[0])
for row in range(1, m):
for col in range(1, n):
if matrix[row][col] != matrix[row - 1][col - 1]:
return False
return True
Complexity
- Time: O(m × n)
- Space: O(1)
- Notes: Most elegant solution with single pass through the matrix
Approach 3: Hash Map by Diagonal Index
Intuition Elements on the same diagonal have the same difference (row - col). Use a hash map to store the expected value for each diagonal and verify consistency.
Steps
- Create a hash map to store values for each diagonal (keyed by row - col)
- Iterate through all elements in the matrix
- For each element, check if its diagonal already has a value stored
- If stored value differs from current element, return false
- Otherwise, store the current element as the expected value for that diagonal
- Return true if all elements are consistent
class Solution:
def isToeplitzMatrix(self, matrix):
m, n = len(matrix), len(matrix[0])
diagonal = {}
for row in range(m):
for col in range(n):
key = row - col
if key in diagonal:
if diagonal[key] != matrix[row][col]:
return False
else:
diagonal[key] = matrix[row][col]
return True
Complexity
- Time: O(m × n)
- Space: O(m + n)
- Notes: Uses extra space for hash map but provides clear conceptual mapping of diagonals