Toeplitz Matrix solution and explanation
TCS
Google
9 more videos on this problem
TOEPLITZ MATRIX | LEETCODE # 766 | PYTHON SOLUTIONCracking FAANG · 8:16 · 8K views
Toeplitz Matrix (Leetcode #766)Programmer Mitch · 9:35 · 7K views
Leetcode 766. Toeplitz Matrix [Java] | Leetcode Easyif else statement · 4:28 · 1K views
LeetCode 766: Toeplitz Matrix in PythonThe Coding Manual - ICCEICQ · 6:38 · 1K views
LeetCode 766. Toeplitz MatrixHappy Coding · 11:07 · 931 views
Leetcode 766 - Toeplitz Matrix (JAVA Solution Explained!)LC Bear · 4:36 · 667 views
766. Toeplitz Matrix || Leetcode || C++Code with Sky · 5:19 · 523 views
Toeplitz Matrix - LeetCode 766 - JavaScriptAlgoJS · 3:59 · 474 views
Daily Leetcode #944: Oct 31, 2022 - 766. Toeplitz MatrixProgramming Live with Larry · 5:35 · 426 views
LeetCode 766. Toeplitz Matrix | JavaScript & AlgorithmJSer · 13:39 · 214 views
The problem
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.
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.lengthn == matrix[i].length1 <= m, n <= 200 <= matrix[i][j] <= 99
Follow up:
- What if the
matrixis stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once? - What if the
matrixis so large that you can only load up a partial row into the memory at once?
Approach overview
Problem Overview: A matrix is called a Toeplitz matrix if every diagonal from top-left to bottom-right contains the same element. Given an matrix, verify that each diagonal has identical values. If any diagonal contains different numbers, the matrix is not Toeplitz.
Approach 1: Iterative Check for Diagonal Consistency (Time: O(m*n), Space: O(1))
The simplest observation: every element should match the element diagonally above it. For any cell matrix[i][j], the previous element on the same diagonal is matrix[i-1][j-1]. Iterate through the matrix starting from row 1 and column 1. If you ever find matrix[i][j] != matrix[i-1][j-1], the Toeplitz property is violated.
This works because each diagonal progresses exactly one step down and one step right. Instead of explicitly traversing diagonals, you compare each element with its top-left neighbor during a single pass through the grid. The algorithm uses a straightforward nested loop over the array structure and performs constant-time comparisons.
This approach runs in O(m*n) time since every cell is visited once, and it uses O(1) extra space because no additional data structures are required. For most interview scenarios and production code, this is the cleanest and most efficient solution.
Approach 2: Use HashMap to Track Diagonals (Time: O(m*n), Space: O(m+n))
Each diagonal in a matrix can be uniquely identified by the difference row - col. All elements with the same value of row - col belong to the same diagonal. You can store the first value encountered for each diagonal in a hash map.
Traverse the matrix once. For each cell, compute key = row - col. If the key is not present in the map, store the current value as the expected value for that diagonal. If it already exists, compare the stored value with the current cell. A mismatch means the matrix is not Toeplitz.
This technique explicitly groups elements by diagonals instead of relying on neighbor comparisons. The time complexity remains O(m*n), but the map stores up to m+n-1 diagonals, giving O(m+n) space usage. It is useful when diagonal grouping logic is needed for extensions of the problem.
Recommended for interviews: The iterative comparison approach is what interviewers typically expect. It demonstrates that you recognize the diagonal relationship matrix[i][j] == matrix[i-1][j-1] and can validate the matrix in a single pass with constant space. The hash map method still works and shows understanding of diagonal indexing, but it introduces unnecessary memory overhead for this specific problem.
Approach 1: Approach 1: Iterative Check for Diagonal Consistency
This method involves checking each element of the matrix to ensure that it equals the element diagonally ahead of it - that is, for each cell matrix[i][j], it should be equal to matrix[i+1][j+1], provided both indices are within bounds.
def isToeplitzMatrix(matrix):
for i in range(len(matrix) - 1):
for j in range(len(matrix[0]) - 1):
if matrix[i][j] != matrix[i + 1][j + 1]:
return False
return Trueclass Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length - 1; i++) {
for (int j = 0; j < matrix[i].length - 1; j++) {
if (matrix[i][j] != matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}
}#include <vector>
using namespace std;
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
for (int i = 0; i < rows - 1; ++i) {
for (int j = 0; j < cols - 1; ++j) {
if (matrix[i][j] != matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}function isToeplitzMatrix(matrix) {
for (let i = 0; i < matrix.length - 1; i++) {
for (let j = 0; j < matrix[0].length - 1; j++) {
if (matrix[i][j] !== matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}#include <stdbool.h>
bool isToeplitzMatrix(int** matrix, int matrixRowSize, int *matrixColSizes) {
for (int i = 0; i < matrixRowSize - 1; i++) {
for (int j = 0; j < matrixColSizes[i] - 1; j++) {
if (matrix[i][j] != matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}public class Solution {
public bool IsToeplitzMatrix(int[][] matrix) {
for (int i = 0; i < matrix.Length - 1; i++) {
for (int j = 0; j < matrix[i].Length - 1; j++) {
if (matrix[i][j] != matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}
}This Python solution similarly traverses the matrix and compares each element to its diagonal successor. If any mismatch is found, it returns False.
Time Complexity: O(m * n)
Space Complexity: O(1)
Approach 2: Approach 2: Use HashMap to Track Diagonals
We can use a HashMap (or dictionary) to maintain the first element of each diagonal. Each key represents the difference between row and column indices, and the value is the first element at this diagonal. While iterating, if a new element violates this rule, the matrix isn't Toeplitz.
def isToeplitzMatrix(matrix):
diagonal_map = {}
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i - j not in diagonal_map:
diagonal_map[i - j] = matrix[i][j]
elif diagonal_map[i - j] != matrix[i][j]:
return False
return Trueimport java.util.HashMap;
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
HashMap<Integer, Integer> diagonalMap = new HashMap<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
int diff = i - j;
if (!diagonalMap.containsKey(diff)) {
diagonalMap.put(diff, matrix[i][j]);
} else if (diagonalMap.get(diff) != matrix[i][j]) {
return false;
}
}
}
return true;
}
}In this Python implementation, a dictionary keeps track of each diagonal. The key (i - j) refers to a specific diagonal, and its value is the element that should be the same for all elements in this diagonal.
Time Complexity: O(m * n)
Space Complexity: O(m + n) for storing diagonal mappings.
Approach 3: Single Traversal
According to the problem description, the characteristic of a Toeplitz matrix is that each element is equal to the element in its upper left corner. Therefore, we only need to iterate through each element in the matrix and check if it is equal to the element in its upper left corner.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
function isToeplitzMatrix(matrix: number[][]): boolean {
const [m, n] = [matrix.length, matrix[0].length];
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
if (matrix[i][j] !== matrix[i - 1][j - 1]) {
return false;
}
}
}
return true;
}func isToeplitzMatrix(matrix [][]int) bool {
m, n := len(matrix), len(matrix[0])
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] != matrix[i-1][j-1] {
return false
}
}
}
return true
}impl Solution {
pub fn is_toeplitz_matrix(matrix: Vec<Vec<i32>>) -> bool {
let (m, n) = (matrix.len(), matrix[0].len());
for i in 1..m {
for j in 1..n {
if matrix[i][j] != matrix[i - 1][j - 1] {
return false;
}
}
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Check for Diagonal Consistency | Time Complexity: O(m * n) |
| Approach 2: Use HashMap to Track Diagonals | Time Complexity: O(m * n) |
| Single Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Check for Diagonal Consistency | O(m*n) | O(1) | Best general solution. Minimal memory usage and a single pass through the matrix. |
| HashMap to Track Diagonals | O(m*n) | O(m+n) | Useful when explicitly grouping or processing diagonals by index. |
Frequently asked questions
Is Toeplitz Matrix easy or hard?
Toeplitz Matrix is classified as an Easy problem on LeetCode with an acceptance rate around 69%. The challenge mainly tests your ability to recognize the diagonal relationship between matrix elements and implement a clean traversal.
How to solve Toeplitz Matrix in O(n)?
A full verification requires checking every element, so the overall complexity is O(m*n). The efficient trick is comparing each cell with matrix[i-1][j-1], which validates all diagonals in one pass without storing extra data.
What is the best approach for Toeplitz Matrix?
The best approach compares each element with its top-left neighbor while iterating through the matrix. If matrix[i][j] ever differs from matrix[i-1][j-1], the Toeplitz property breaks. This method runs in O(m*n) time with O(1) extra space and is the standard interview solution.
Is Toeplitz Matrix asked at Google/Amazon/Meta?
Toeplitz Matrix appears in coding interviews at companies that test matrix traversal and pattern recognition. Variants of this problem have shown up in interviews at Amazon, Google, and other large tech companies focusing on array and matrix fundamentals.
What data structure is used in Toeplitz Matrix?
The most efficient solution uses only the input matrix and simple index comparisons. An alternative solution uses a hash map keyed by (row - column) to track values belonging to the same diagonal.
What is the time complexity of Toeplitz Matrix?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is visited exactly once and compared with its top-left neighbor. Space complexity is O(1) for the iterative method.
Toeplitz Matrix Python or Java solution approach?
Both Python and Java implementations typically use the same logic: iterate through the matrix starting from index (1,1) and compare each value with matrix[i-1][j-1]. This produces an O(m*n) time and O(1) space solution in either language.