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] <= 99Follow 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?In #766 Toeplitz Matrix, the goal is to determine whether every diagonal from the top-left to the bottom-right contains the same value. A matrix is considered Toeplitz if each element matches the element diagonally up-left from it.
The most straightforward idea is to iterate through the matrix and compare each element matrix[i][j] with its top-left neighbor matrix[i-1][j-1]. If any pair differs, the matrix is not Toeplitz. Since the first row and first column do not have top-left neighbors, comparisons start from index (1,1). This approach efficiently validates all diagonals in a single pass.
An alternative conceptual approach is to track diagonals using a map keyed by i - j, since elements on the same diagonal share the same difference. Both strategies work well, but the direct comparison approach is simpler and uses constant extra space.
The traversal visits each cell once, leading to O(m × n) time complexity and O(1) additional space for the optimal solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Neighbor Diagonal Comparison | O(m × n) | O(1) |
| Hash Map by Diagonal (i - j) | O(m × n) | O(min(m, n)) |
Programmer Mitch
Use these hints if you're stuck. Try solving on your own first.
Check whether each value is equal to the value of it's top-left neighbor.
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.
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.
1#include <stdbool.h>
2
3bool isToeplitzMatrix(int** matrix, int matrixRowSize, int *matrixColSizes) {
4 for (int i = 0In 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.
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.
Time Complexity: O(m * n)
Space Complexity: O(m + n) for storing diagonal mappings.
1def isToeplitzMatrix(matrix):
2 diagonal_map = {Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of matrix validation problems like Toeplitz Matrix are commonly asked in technical interviews. They test understanding of matrix traversal, indexing patterns, and edge-case handling.
The optimal approach checks whether each element matches its top-left diagonal neighbor. By iterating from the second row and second column and comparing matrix[i][j] with matrix[i-1][j-1], we can validate the Toeplitz property in a single pass with constant extra space.
A simple 2D array traversal is sufficient for the optimal solution. Alternatively, a hash map keyed by the diagonal index (i - j) can be used to group elements belonging to the same diagonal.
For any element in a matrix, moving one step down and one step right increases both row and column indices equally. This keeps the difference (i - j) constant, which uniquely identifies a top-left to bottom-right diagonal.
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.