Toeplitz Matrix Solution

Problem Description

Given an m x n matrix, determine if it is a Toeplitz matrix. A Toeplitz matrix has the property where each diagonal from top-left to bottom-right has the same elements.

Brute Force Solution

The brute force solution involves iterating through each diagonal and checking if all elements in that diagonal are the same. This can be done by comparing each element with the first element of the diagonal.

Algorithm

1. Iterate through the first column of the matrix (starting points for diagonals).
2. For each starting point, check if the diagonal elements are the same.
3. Iterate through the first row of the matrix (starting points for diagonals, excluding the top-left which has already been checked).
4. For each starting point, check if the diagonal elements are the same.
5. If any diagonal violates the Toeplitz property, return false. Otherwise, return true.

Code (Python)

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        rows, cols = len(matrix), len(matrix[0])

        def check_diagonal(row_start, col_start):
            value = matrix[row_start][col_start]
            row, col = row_start, col_start
            while row < rows and col < cols:
                if matrix[row][col] != value:
                    return False
                row += 1
                col += 1
            return True

        # Check diagonals starting from the first column
        for i in range(rows):
            if not check_diagonal(i, 0):
                return False

        # Check diagonals starting from the first row (excluding the first element)
        for j in range(1, cols):
            if not check_diagonal(0, j):
                return False

        return True

Time Complexity

O(m * n), where m is the number of rows and n is the number of columns.

Space Complexity

O(1), as it uses constant extra space.

Optimal Solution

The optimal solution involves comparing each element with its top-left neighbor. If any element is different from its top-left neighbor, the matrix is not Toeplitz.

Algorithm

1. Iterate through the matrix, starting from the second row and second column.
2. For each element, compare it with the element at matrix[i-1][j-1].
3. If they are not equal, return false.
4. If the entire matrix is checked and no discrepancy is found, return true.

Code (Python)

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        rows, cols = len(matrix), 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

Time Complexity

O(m * n), where m is the number of rows and n is the number of columns.

Space Complexity

O(1), as it uses constant extra space.

Edge Cases

• Empty Matrix: If the matrix is empty (either 0 rows or 0 columns), it can be considered a Toeplitz matrix.
• Single Element Matrix: If the matrix has only one element, it is a Toeplitz matrix.
• Single Row or Single Column Matrix: Any single row or single column matrix is considered a Toeplitz matrix.

Follow-up questions

• 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?
  • In this case, read the first row into memory. Then for each subsequent row, compare each element with the corresponding element from the previous row (which is in memory) at the appropriate offset. This way, you only need to keep one row in memory at a time.
• What if the matrix is so large that you can only load up a partial row into the memory at once?
  • Split the problem into smaller subproblems, processing chunks of rows and comparing overlaps appropriately. More complex logic is required here involving keeping track of partial diagonal information.