Skip to main content
Talentd

Toeplitz Matrix - Solution & Explanation

EasyArrayMatrix12 min readAsked at: Meta, Wipro, Google +1
Practice this problem

Problem Statement

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.length
  • n == matrix[i].length
  • 1 <= m, n <= 20
  • 0 <= matrix[i][j] <= 99

 

Follow up:

  • What if the matrix is 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 matrix is 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.

In C, we use nested loops to iterate over each element, excluding the last row and column, to check if matrix[i][j] equals matrix[i+1][j+1]. If any element fails this check, we immediately return false.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(1), since no additional data structures are used.

Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(m * n)
Space Complexity: O(m + n) for storing diagonal mappings.

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Iterative Check for Diagonal Consistency

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(1), since no additional data structures are used.

Approach 2: Use HashMap to Track Diagonals

Time Complexity: O(m * n)
Space Complexity: O(m + n) for storing diagonal mappings.

Single Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Check for Diagonal ConsistencyO(m*n)O(1)Best general solution. Minimal memory usage and a single pass through the matrix.
HashMap to Track DiagonalsO(m*n)O(m+n)Useful when explicitly grouping or processing diagonals by index.

Video Solution

TOEPLITZ MATRIX | LEETCODE # 766 | PYTHON SOLUTION • Cracking FAANG • 8,926 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Toeplitz Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Word Square