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:
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?matrix is so large that you can only load up a partial row into the memory at once?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.
C++
Java
Python
C#
JavaScript
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.
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.
Java
Time Complexity: O(m * n)
Space Complexity: O(m + n) for storing diagonal mappings.
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Check for Diagonal Consistency | Time Complexity: O(m * n) where |
| Approach 2: Use HashMap to Track Diagonals | Time Complexity: O(m * n) |
Toeplitz Matrix (Leetcode #766) • Programmer Mitch • 7,700 views views
Watch 9 more video solutions →Practice Toeplitz Matrix with our built-in code editor and test cases.
Practice on FleetCode