Toeplitz Matrix

Problem Statement

The problem requires us to determine if a given m x n matrix qualifies as a Toeplitz matrix. A Toeplitz matrix is characterized by each of its diagonals (running from the top-left corner to the bottom-right corner) having identical elements. In simple terms, if you pick any diagonal in the matrix, all elements along that diagonal should be the same. The objective is to return true if the matrix is Toeplitz, otherwise return false.

Examples

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

Approach and Intuition

To determine if a matrix is a Toeplitz matrix, you can take the following steps based on the examples provided:

1. Iterate through each element in the matrix except for those in the last row and last column. This is because these elements have no diagonals extending to the bottom-right that need checking.
2. For each element at position (i, j), compare it with the element at position (i + 1, j + 1). This is effectively checking if the current element is the same as the next one in its diagonal.
3. If any of these comparisons fail (i.e., the elements are not the same), immediately return false.
4. If all comparisons pass, return true after the loop completes.

Example Analysis

• Example 1: For the matrix [[1,2,3,4],[5,1,2,3],[9,5,1,2]], the comparisons would be between elements (0,0) and (1,1), (0,1) and (1,2), (0,2) and (1,3), (1,0) and (2,1), and so on. All these pairs consist of identical elements, thus the matrix is Toeplitz and returns true.

• Example 2: For the matrix [[1,2],[2,2]], comparing element (0,0) with (1,1) shows a difference (1 ≠ 2), which makes the matrix non-Toeplitz. Therefore, it returns false.

Using this approach, we can systematically determine the Toeplitz property of any matrix conforming to the given constraints, which include matrix dimensions up to 20x20 and element values between 0 and 99.

Solutions

class Solution {
    public boolean checkToeplitz(int[][] mtx) {
        for (int row = 0; row < mtx.length; row++)
            for (int col = 0; col < mtx[0].length; col++)
                if (row > 0 && col > 0 && mtx[row-1][col-1] != mtx[row][col])
                    return false;
        return true;
    }
}