{x}
blog image

Toeplitz Matrix

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.

 

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

 

Follow up:

  • What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
  • What if the matrix is so large that you can only load up a partial row into the memory at once?

Solution Explanation

The problem asks to determine if a given matrix is a Toeplitz matrix. A Toeplitz matrix is one where each diagonal from top-left to bottom-right has the same elements. The solution involves iterating through the matrix and checking if this condition holds true.

Approach

The most straightforward approach is to compare each element with the element diagonally above and to the left of it. If any pair of elements doesn't match, the matrix is not Toeplitz.

The code iterates through the matrix, starting from the second row and second column (index 1). It compares matrix[i][j] with matrix[i-1][j-1]. If they are different, it immediately returns false. If the loop completes without finding any mismatches, it means the matrix is Toeplitz, and the function returns true.

Code Explanation (Python as Example)

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m, n = len(matrix), len(matrix[0])
        return all(
            matrix[i][j] == matrix[i - 1][j - 1]
            for i in range(1, m)
            for j in range(1, n)
        )

  • m, n = len(matrix), len(matrix[0]): This line gets the dimensions of the matrix. m is the number of rows, and n is the number of columns.

  • return all(...): This uses the all() function to efficiently check the condition for all elements. The generator expression (matrix[i][j] == matrix[i - 1][j - 1] for i in range(1, m) for j in range(1, n)) iterates through the matrix, starting from the second row and second column, and yields True if the current element is equal to the diagonally top-left element, and False otherwise. all() returns True only if all yielded values are True.

Time and Space Complexity

  • Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns. The code iterates through the matrix once.

  • Space Complexity: O(1). The solution uses a constant amount of extra space, regardless of the matrix size. The all() function might use a small amount of stack space for the generator, but this is considered constant in relation to the input size.

The same logic and complexity analysis apply to the solutions provided in Java, C++, Go, and JavaScript. They all achieve the same result using nested loops to efficiently check the Toeplitz property.