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.

Examples

Example 1:

$$ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 1 & 2 & 3 \\ 9 & 5 & 1 & 2 \end{bmatrix} $$

1
2
3
4
5
6

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: $$ \begin{bmatrix} 1 & 2 \\ 2 & 2 \end{bmatrix} $$

1
2
3
4

Input: matrix = [[1,2],[2,2]]
Output: false
Explanation:
The diagonal "[1, 2]" has different elements.

Solution

Method 1 - Iteration

We can iterate through each element in the matrix (except the last row and last column) and checks if the current element matrix[i][j] is equal to the element to its bottom-right diagonal matrix[i+1][j+1]. If any elements do not match, it returns False. If all elements match the condition, it returns True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public boolean isToeplitzMatrix(int[][] matrix) {
	for (int i = 0; i < matrix.length - 1; i++) {
		for (int j = 0; j < matrix[i].length - 1; j++) {
			if (matrix[i][j] != matrix[i + 1][j + 1]) {
				return false;
			}
		}
	}

	return true;
}
1
2
3
4
5
6

 def is_toeplitz_matrix(matrix):
     for i in range(len(matrix) - 1):
         for j in range(len(matrix[i]) - 1):
             if matrix[i][j] != matrix[i + 1][j + 1]:
                 return False
     return True

Complexity

  • ⏰ Time complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. The function iterates through nearly all elements of the matrix once.
  • 🧺 Space complexity: O(1), The space complexity is constant because no additional space proportional to the input size is used. The function only uses a fixed amount of extra space for variables i and j.