# Toeplitz Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/toeplitz-matrix)
Canonical: https://scaleengineer.com/dsa/problems/toeplitz-matrix
**Data structures:** Array, Matrix
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
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:**

![](https://assets.glich.co/dsa/toeplitz-matrix/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/toeplitz-matrix/image1.jpg) 

**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
## Group by Diagonal (Hash Map)
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`.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Compare with Top-Left Neighbor
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (matrix[r][c] != matrix[r-1][c-1]) {
                    return false;
                }
            }
        }
        return true;
    }
}
```

### 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:
1. Read the first row (row 0) from disk into a buffer, let's call it `prev_row`.
2. 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.
3. 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.
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {boolean} */ var isToeplitzMatrix =
  function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    for (let i = 1; i < m; ++i) {
      for (let j = 1; j < n; ++j) {
        if (matrix[i][j] != matrix[i - 1][j - 1]) {
          return false;
        }
      }
    }
    return true;
  };

```

### CPP

```cpp
class Solution {
public:
  bool isToeplitzMatrix(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    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;
  }
};

```

### Python

```python
class Solution:
    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))

```