Toeplitz Matrix
EasyPrompt
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?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves identifying all elements belonging to the same diagonal and checking if they are all identical. We can use a hash map to group elements by their diagonal index, which can be calculated as row - column.
Algorithm
- Create a hash map
diagonalsto store the first element encountered for each diagonal. - Iterate through each cell
(r, c)of the matrix. - Calculate the diagonal identifier
diagId = r - c. - If
diagIdis not indiagonals, addmatrix[r][c]to the map with keydiagId. - If
diagIdis already indiagonals, check if the stored value is equal tomatrix[r][c]. If not, returnfalse. - If the entire matrix is traversed without returning
false, returntrue.
Walkthrough
In a Toeplitz matrix, all elements on a given top-left to bottom-right diagonal are the same. A key observation is that for any element matrix[r][c], all other elements on the same diagonal will have the same value for the expression r - c. We can use this property as a key to group elements by their diagonal.
We can iterate through the entire matrix, and for each element matrix[r][c], we calculate its diagonal ID d = r - c. We use a hash map to store the value of the first element we encounter for each diagonal. For subsequent elements on the same diagonal, we compare their value with the one stored in the hash map. If we find a mismatch, the matrix is not Toeplitz. If we traverse the whole matrix without any mismatches, it is a Toeplitz matrix.
import java.util.HashMap;import java.util.Map; class Solution { public boolean isToeplitzMatrix(int[][] matrix) { Map<Integer, Integer> diagonals = new HashMap<>(); int m = matrix.length; int n = matrix[0].length; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { int diagId = r - c; if (!diagonals.containsKey(diagId)) { diagonals.put(diagId, matrix[r][c]); } else { if (diagonals.get(diagId) != matrix[r][c]) { return false; } } } } return true; }}Complexity
Time
O(m * n), where `m` is the number of rows and `n` is the number of columns. We need to visit every element in the matrix once.
Space
O(m + n). The number of diagonals in an `m x n` matrix is `m + n - 1`. In the worst case, the hash map will store one entry for each diagonal.
Trade-offs
Pros
Conceptually straightforward, as it directly models the definition of diagonals.
Cons
Requires extra space proportional to the number of diagonals, which is less efficient than the optimal approach.
Solutions
Solution
class Solution {public boolean isToeplitzMatrix(int[][] matrix) { int m = matrix.length, n = matrix[0].length; for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] != matrix[i - 1][j - 1]) { return false; } } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.