Toeplitz Matrix

Easy

#0720Time: 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.1 company

Data structures

Array Matrix

Companies

tcs

Prompt

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?

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 diagonals to 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 diagId is not in diagonals, add matrix[r][c] to the map with key diagId.
If diagId is already in diagonals, check if the stored value is equal to matrix[r][c]. If not, return false.
If the entire matrix is traversed without returning false, return true.

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean isToeplitzMatrix(int[][] matrix) {6        Map<Integer, Integer> diagonals = new HashMap<>();7        int m = matrix.length;8        int n = matrix[0].length;9 10        for (int r = 0; r < m; r++) {11            for (int c = 0; c < n; c++) {12                int diagId = r - c;13                if (!diagonals.containsKey(diagId)) {14                    diagonals.put(diagId, matrix[r][c]);15                } else {16                    if (diagonals.get(diagId) != matrix[r][c]) {17                        return false;18                    }19                }20            }21        }22        return true;23    }24}

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.

A more efficient approach is to directly check the property of a Toeplitz matrix. For any element in the matrix (except those in the first row and first column), it must be equal to its top-left neighbor. By iterating through the matrix and performing this check, we can determine if it's a Toeplitz matrix without using extra space.

Algorithm

Iterate through the matrix starting from the second row and second column (index 1).
For each element matrix[r][c], compare it with the element at its top-left, matrix[r-1][c-1].
If matrix[r][c] is not equal to matrix[r-1][c-1], the matrix is not Toeplitz, so return false.
If the loops complete without finding any mismatches, it means the matrix is Toeplitz. Return true.

Walkthrough

The defining property of a Toeplitz matrix is that each element is the same as the one on its top-left. That is, for any r > 0 and c > 0, matrix[r][c] == matrix[r-1][c-1]. The elements in the first row and first column do not have a top-left neighbor, so they serve as the reference values for their respective diagonals.

We can simply iterate through the matrix, starting from (1, 1), and for each element, we compare it with its top-left neighbor. If we find any pair (matrix[r][c], matrix[r-1][c-1]) that are not equal, we can immediately conclude the matrix is not Toeplitz and return false. If we complete the iteration over all such elements without finding any mismatch, the matrix must be Toeplitz, and we can return true.

1class Solution {2    public boolean isToeplitzMatrix(int[][] matrix) {3        int m = matrix.length;4        int n = matrix[0].length;5 6        for (int r = 1; r < m; r++) {7            for (int c = 1; c < n; c++) {8                if (matrix[r][c] != matrix[r-1][c-1]) {9                    return false;10                }11            }12        }13        return true;14    }15}

Follow-up Questions

Handling Memory Constraints (One Row at a Time)

If the matrix is stored on disk and we can only load one row into memory at a time, we can adapt this approach. The check matrix[r][c] == matrix[r-1][c-1] requires us to know about the previous row (r-1) when processing the current row (r).

We can use a buffer in memory of size n (the number of columns) to store the previous row. The algorithm would be:

Read the first row (row 0) from disk into a buffer, let's call it prev_row.
For each subsequent row r from 1 to m-1: a. Read the current row r from disk into another buffer, current_row. b. Compare elements: for c from 1 to n-1, check if current_row[c] != prev_row[c-1]. If they are not equal, return false. c. After the checks, update prev_row with the contents of current_row to be used for the next iteration.
If the loop completes, return true.

This approach makes a single sequential pass over the data on disk and uses O(n) extra space for the buffers, which fits the constraint.

Handling Severe Memory Constraints (Partial Row at a Time)

If the memory is so limited that we cannot even store a full row (i.e., memory is o(n)), the problem becomes more challenging. We face a trade-off between I/O patterns and memory usage.

Random Access Approach: We can iterate through each of the m + n - 1 diagonals one by one. For each diagonal, we read its first element, then seek to the position of the next element on the same diagonal on disk and read it, comparing the two. We repeat this for all elements on the diagonal. This uses O(1) memory but requires random disk access for almost every element read, which is extremely slow due to disk seek times.
Sequential Access Approach: To maintain sequential reads, more complex external memory algorithms would be needed. For example, one could make multiple passes over the data. In one pass, create a temporary file containing row_r[1:] for all r > 0. In another pass, create a file with row_{r-1}[:-1] for all r > 0. Then, a final pass could compare these two temporary files. This maintains sequential I/O but at the cost of significantly more I/O operations and temporary disk space.

Complexity

Time

O(m * n), where `m` is the number of rows and `n` is the number of columns. We iterate through almost every cell once to perform a single comparison.

Space

O(1). This approach uses only a constant amount of extra space for loop variables and indices, regardless of the matrix size.

Trade-offs

Pros

Highly space-efficient, using O(1) extra space.
Simple to understand and implement.
Optimal in terms of time complexity.

Cons

None for the given constraints. It is the optimal solution.

Solutions

Solution

1class Solution {2public3  boolean isToeplitzMatrix(int[][] matrix) {4    int m = matrix.length, n = matrix[0].length;5    for (int i = 1; i < m; ++i) {6      for (int j = 1; j < n; ++j) {7        if (matrix[i][j] != matrix[i - 1][j - 1]) {8          return false;9        }10      }11    }12    return true;13  }14}

1/** * @param {number[][]} matrix * @return {boolean} */ var isToeplitzMatrix =2  function (matrix) {3    const m = matrix.length;4    const n = matrix[0].length;5    for (let i = 1; i < m; ++i) {6      for (let j = 1; j < n; ++j) {7        if (matrix[i][j] != matrix[i - 1][j - 1]) {8          return false;9        }10      }11    }12    return true;13  };

1class Solution {2public:3  bool isToeplitzMatrix(vector<vector<int>> &matrix) {4    int m = matrix.size(), n = matrix[0].size();5    for (int i = 1; i < m; ++i) {6      for (int j = 1; j < n; ++j) {7        if (matrix[i][j] != matrix[i - 1][j - 1]) {8          return false;9        }10      }11    }12    return true;13  }14};

1class Solution:2    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool: m, n = len(matrix), len(matrix[0]) return all(matrix[i][j] == matrix[i - 1][j - 1] for i in range(1, m) for j in range(1, n))

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.

← Previous

Previous problem

Next problem