Code Implementation

class Solution:
    def isToeplitzMatrix(self, matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] != matrix[i-1][j-1]:
                    return False
        return True
      

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        for (int i = 1; i < rows; ++i) {
            for (int j = 1; j < cols; ++j) {
                if (matrix[i][j] != matrix[i-1][j-1]) {
                    return false;
                }
            }
        }
        return true;
    }
};
      

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

var isToeplitzMatrix = function(matrix) {
    let rows = matrix.length, cols = matrix[0].length;
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][j] !== matrix[i-1][j-1]) {
                return false;
            }
        }
    }
    return true;
};
      

Problem Description

Given a 2D array matrix, determine if it is a Toeplitz matrix. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. In other words, for all valid i and j, matrix[i][j] == matrix[i-1][j-1] whenever i > 0 and j > 0.

• Input: 2D integer array matrix with at least 1 row and 1 column.
• Output: true if matrix is Toeplitz, false otherwise.
• Constraints: Only check diagonals from top-left to bottom-right. Do not compare elements outside the matrix bounds.

Thought Process

The core idea is to verify that every diagonal (from top-left to bottom-right) has the same value. A brute-force approach might involve collecting all diagonals and checking their values, but that's unnecessary. Instead, we can observe that for any cell (i, j) (except those in the first row or first column), its value should match the value in the cell directly up-and-left, i.e., (i-1, j-1). If we find any mismatch, the matrix is not Toeplitz.

This insight allows us to avoid extra data structures or diagonal tracking. We just compare each cell (except those in the first row or column) with its top-left neighbor.

Solution Approach

Here’s how we can solve the problem efficiently:

1. Iterate through the matrix starting from i = 1 and j = 1 to avoid the first row and column (which have no upper-left neighbors).
2. For each cell (i, j), compare matrix[i][j] with matrix[i-1][j-1].
3. If any comparison fails (the values differ), immediately return false.
4. If all comparisons pass, return true at the end.

This approach is efficient because:

• We only use two nested loops, iterating over each cell once.
• No extra space is required beyond a few variables.

Example Walkthrough

Example:
Input:

    matrix = [
      [1, 2, 3, 4],
      [5, 1, 2, 3],
      [9, 5, 1, 2]
    ]
    

• Cell (1,1): 1 == 1 (top-left), OK
• Cell (1,2): 2 == 2 (top-left), OK
• Cell (1,3): 3 == 3 (top-left), OK
• Cell (2,1): 5 == 5 (top-left), OK
• Cell (2,2): 1 == 1 (top-left), OK
• Cell (2,3): 2 == 2 (top-left), OK

Counter-example:
Input:

    matrix = [
      [1, 2],
      [2, 2]
    ]
    

• Cell (1,1): 2 != 1 (top-left), so return false.

Time and Space Complexity

• Brute-force: If we explicitly collect and check all diagonals, we may need extra space for each diagonal and iterate over all elements, leading to O(mn) time and O(m+n) space (for m rows, n columns).
• Optimized: The implemented approach checks each cell once (except the first row/column), so time complexity is O(mn). No extra data structures are used, so space complexity is O(1) (ignoring input).

Summary

The Toeplitz Matrix problem is efficiently solved by simply comparing each cell to its top-left neighbor, leveraging the definition of a Toeplitz matrix. This approach is both intuitive and optimal, requiring only a double loop and no extra space. The key insight is that the property of all diagonals being equal can be checked locally, making the solution elegant and efficient.