Leetcode 766. Toeplitz Matrix
Problem Explanation:
A matrix is a 2D grid of values. In this problem, we are given a 2D matrix of integers and we have to determine if the matrix is a Toeplitz matrix or not. A matrix is said to be a Toeplitz matrix if every diagonal from the top-left to the bottom-right has the same element. We need to return True
if the matrix is Toeplitz, otherwise False
.
Let's consider a example, given a matrix:
1matrix = [ 2 [1,2,3,4], 3 [5,1,2,3], 4 [9,5,1,2] 5]
The diagonals from the top-left to the bottom-right are [9]
,[5, 5]
,[1, 1, 1]
,[2, 2, 2]
,[3, 3]
,[4]
. In each diagonal all elements are the same. Hence, the matrix is a Toeplitz matrix and the answer is True
.
Approach:
We have to ensure that every diagonal from top-left to bottom-right has the same elements. In order to do this, we need to iterate over each element in the matrix and check if it is equal to the element in the next diagonal. If it is, we move to the next element. If it's not, we return False
, since the matrix can't be a Toeplitz matrix.
Python Solution:
1 2python 3class Solution: 4 def isToeplitzMatrix(self, matrix: [[int]]) -> bool: 5 for i in range(len(matrix) - 1): 6 for j in range(len(matrix[i]) - 1): 7 # Check if a matrix element is not equal to next diagonal element 8 if matrix[i][j] != matrix[i + 1][j + 1]: 9 return False 10 return True
Java Solution:
1
2java
3class Solution {
4
5 public boolean isToeplitzMatrix(int[][] matrix) {
6 for (int i = 0; i < matrix.length - 1; i++) {
7 for (int j = 0; j < matrix[i].length - 1; j++) {
8 // Check if a matrix element is not equal to next diagonal element
9 if (matrix[i][j] != matrix[i + 1][j + 1]) {
10 return false;
11 }
12 }
13 }
14 return true;
15 }
16}
JavaScript Solution:
1
2javascript
3class Solution {
4 isToeplitzMatrix(matrix) {
5 for (let i = 0; i < matrix.length - 1; i++) {
6 for (let j = 0; j < matrix[i].length - 1; j++) {
7 // Check if a matrix element is not equal to next diagonal element
8 if (matrix[i][j] != matrix[i + 1][j + 1]) {
9 return false;
10 }
11 }
12 }
13 return true;
14 }
15}
C++ Solution:
1
2c++
3class Solution {
4public:
5 bool isToeplitzMatrix(vector<vector<int>>& matrix) {
6 for (int i = 0; i < matrix.size() - 1; ++i)
7 for (int j = 0; j < matrix[0].size() - 1; ++j)
8 // Check if a matrix element is not equal to next diagonal element
9 if (matrix[i][j] != matrix[i + 1][j + 1])
10 return false;
11 return true;
12 }
13};
C# Solution:
1
2csharp
3public class Solution {
4 public bool IsToeplitzMatrix(int[][] matrix) {
5 for (int i = 0; i < matrix.Length - 1; i++) {
6 for (int j = 0; j < matrix[i].Length - 1; j++) {
7 // Check if a matrix element is not equal to next diagonal element
8 if (matrix[i][j] != matrix[i + 1][j + 1]) {
9 return false;
10 }
11 }
12 }
13 return true;
14 }
15}
Ruby Solution:
1 2ruby 3class Solution 4 def is_toeplitz_matrix(matrix) 5 for i in 0..matrix.length-2 do 6 for j in 0..matrix[i].length-2 do 7 # Check if a matrix element is not equal to the next diagonal element 8 if matrix[i][j] != matrix[i + 1][j + 1] 9 return false 10 end 11 end 12 end 13 true 14 end 15end
Above mentioned are the methods to solve the problem for Python, JavaScript, Java, C++, C# and Ruby.
While they all essentially perform the same actions through their respective languages, the underlying logic remains the same: iterate through the matrix checking if the current element is same as the next diagonal element. This validation is done for every element in the matrix minus the last row and column to avoid ArrayOutOfBoundsException or IndexError which could occur by checking for diagonal value at the boundaries.
If any element, is found to have a mismatch with the diagonal value, an early exit is done returning false
, thus eliminating unnecessary iterations.
In the case the validation is successful, the method will end returning true
, indicating the matrix to be a Toeplitz matrix.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.