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.