Today's problem is focused on matrix manipulation. A Toeplitz matrix is a matrix in which each descending diagonal from left to right is constant. Given a matrix, can you write a function to determine if it is a Toeplitz matrix? The function should take the matrix as input and return true if it's a Toeplitz matrix, and false otherwise.

Here are some examples to illustrate the problem:

• Example 1:

  Input: matrix = [ [1,2,3,4], [5,1,2,3], [6,5,1,2] ]

  Output: true

  Explanation: In the above matrix, the diagonals are [6], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3], [4]. Because each diagonal has the same element, it is a Toeplitz matrix.

• Example 2:

  Input: matrix = [ [1,2], [2,2] ]

  Output: false

  Explanation: The diagonal from top-left to bottom-right is [1, 2].

• Example 3:

  Input: [ [36, 59, 71, 15, 26, 82, 88], [28, 36, 59, 71, 15, 26, 82], [13, 28, 36, 59, 71, 15, 26], [52, 13, 28, 36, 59, 71, 15] ]

  Output: false

After you've implemented the function, please analyze the time and space complexity of your solution.

Toeplitz Matrix

Problem Description

A Toeplitz matrix is a matrix in which each descending diagonal from left to right is constant. Given a matrix, determine whether it is a Toeplitz matrix.

1. Naive (Brute Force) Solution

The most straightforward approach is to iterate through the matrix and compare each element with the element diagonally below and to the right. If any pair of such elements are unequal, the matrix is not Toeplitz.

python def is_toeplitz_naive(matrix): rows = len(matrix) cols = len(matrix[0])

for i in range(rows - 1):
    for j in range(cols - 1):
        if matrix[i][j] != matrix[i+1][j+1]:
            return False
return True

2. Optimal Solution

Since all elements on a diagonal have the same value, we only need to check that each element is equal to its top-left neighbor, as long as such neighbor exists.

python def is_toeplitz(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

3. Big(O) Run-time

Both the naive and optimal solutions involve iterating through (almost) every element of the matrix. Therefore, the time complexity is O(m * n), where 'm' is the number of rows and 'n' is the number of columns.

4. Big(O) Space Usage

Both solutions use a constant amount of extra space, regardless of the size of the matrix. Thus, the space complexity is O(1).

5. Edge Cases

• Empty Matrix: An empty matrix can be considered Toeplitz.
• Single Row/Column Matrix: A matrix with only one row or one column is also Toeplitz.
• Null or Invalid Input: The code should handle cases where the input matrix is None or doesn't conform to a rectangular shape.

python def is_toeplitz_robust(matrix): if not matrix: return True

rows = len(matrix)
if rows == 0:
    return True # or raise an exception if the matrix is malformed

cols = len(matrix[0])
if cols == 0:
    return True  # consider this Toeplitz
    
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

6. Code Example (Optimal)

python def is_toeplitz(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

Example usage

matrix1 = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]] matrix2 = [[1, 2], [2, 2]]

print(f"Matrix 1 is Toeplitz: {is_toeplitz(matrix1)}") # Output: True print(f"Matrix 2 is Toeplitz: {is_toeplitz(matrix2)}") # Output: False