Toeplitz Matrix — Solution in Python, Java & C++
Toeplitz Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and matrix.
Toeplitz Matrix is an easy coding problem on arrays and matrix, asked in Amazon, Google and Meta interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A matrix is Toeplitz if every diagonal running from top-left to bottom-right holds the same value throughout.
Given an m × n matrix, return true if it is Toeplitz.
Example 1
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation: Each descending diagonal is constant.
Example 2
Input: matrix = [[1,2],[2,2]]
Output: false
Explanation: The diagonal starting at (0,0) holds 1 then 2.
Example 3
Input: matrix = [[7]]
Output: true
Constraints
1 <= matrix.length, matrix[i].length <= 80 <= matrix[i][j] <= 20
Follow-up: What if the matrix is too large to load into memory at once, and you can only read one row at a time?
Hints for Toeplitz Matrix
Hint 1
You never need to walk a whole diagonal — comparing each cell with its up-left neighbour covers every diagonal.
Hint 2
Start the loops at row 1 and column 1 so the neighbour always exists.
How to solve Toeplitz Matrix
Every diagonal is constant exactly when every cell equals its up-left neighbour.
Approach
- For
rfrom 1 andcfrom 1, comparematrix[r][c]withmatrix[r-1][c-1]. - Return
falseon the first mismatch,trueotherwise.
Why it works
Two consecutive cells on a diagonal differ by (1, 1), so checking each such pair covers every adjacent pair on every diagonal, and constancy along a diagonal follows by induction.
Complexity
- Time —
O(m · n) - Space —
O(1)
Pitfalls
- Starting either loop at 0 reads out of bounds.
- For a matrix streamed one row at a time, compare each row with the previous row shifted by one.
Reference solution
Python
def isToeplitzMatrix(matrix) -> bool:
for r in range(1, len(matrix)):
for c in range(1, len(matrix[0])):
if matrix[r][c] != matrix[r - 1][c - 1]:
return False
return TrueJava
public static boolean isToeplitzMatrix(int[][] matrix) {
for (int r = 1; r < matrix.length; r++) {
for (int c = 1; c < matrix[0].length; c++) {
if (matrix[r][c] != matrix[r - 1][c - 1]) return false;
}
}
return true;
}C++
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
for (size_t r = 1; r < matrix.size(); r++) {
for (size_t c = 1; c < matrix[0].size(); c++) {
if (matrix[r][c] != matrix[r - 1][c - 1]) return false;
}
}
return true;
}JavaScript
var isToeplitzMatrix = function(matrix) {
for (let r = 1; r < matrix.length; r++) {
for (let c = 1; c < matrix[0].length; c++) {
if (matrix[r][c] !== matrix[r - 1][c - 1]) return false;
}
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal