Toeplitz Matrix

LeetCode 777 | Difficulty: Easy

Easy

Problem Description

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?

Topics: Array, Matrix

---

Approach

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 140 ms)

Metric	Value
Runtime	140 ms
Memory	N/A
Date	2018-04-12

Solution

public class Solution {
    public bool IsToeplitzMatrix(int[,] matrix) {
        for (int i = 0; i < matrix.GetLength(0)-1; i++)
    {
        for (int j = 0; j < matrix.GetLength(1)-1; j++)
        {
            if(matrix[i,j] != matrix[i+1,j+1]) return false;
        }
    }
    
    return true;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Check whether each value is equal to the value of it's top-left neighbor.