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.