Toeplitz Matrix
Easy · Matrix · Array · Matrix
Problem
A matrix is Toeplitz when every diagonal that runs from top-left to bottom-right holds a single repeated value.
Given an m x n integer matrix matrix, return true if it is Toeplitz and false otherwise.
Put another way: the matrix is Toeplitz exactly when matrix[i][j] == matrix[i-1][j-1] for every cell that has an upper-left neighbor.
Examples
Input: matrix = [[3,5,6],[2,3,5],[8,2,3]] Output: true
The diagonals are [8], [2,2], [3,3,3], [5,5] and [6], and each holds one value.
Input: matrix = [[1,4],[4,2]] Output: false
The main diagonal holds 1 and 2.
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true
Each row is the row above shifted right by one, so every diagonal repeats one value.
Constraints
- m == len(matrix), n == len(matrix[i])
- 1 <= m, n <= 20
- 0 <= matrix[i][j] <= 99
Approaches
- Walk each diagonal from its start — time O(m·n), space O(1)
Follow-up
If the matrix is so large that only one row fits in memory at a time, compare each row with the previous one shifted by one place: row i from column 1 on must equal row i - 1 up to its last column but one. If only part of a row fits, split the rows into chunks that overlap by one column. The use cases check the other diagonal direction and count the fewest changes that make a matrix Toeplitz.
Related problems
Start free on Cariara · Coding problems · System design studio
