algoadvance

A matrix is called Toeplitz if every diagonal from top-left to bottom-right has the same elements. Now given an m x n matrix, return True if the matrix is Toeplitz. Otherwise, return False.

A matrix can be defined as a two-dimensional array.

Example 1:

Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True

Explanation: In the given matrix, each diagonal from top-left to bottom-right has the same elements.

Example 2:

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

Explanation: The diagonal starting at (0,0) contains 1 and 2 which are different.

Clarifying Questions:

1. What are the constraints on the size of the matrix?
   • Usually, the size of the matrix will be constrained by typical computational limits. However, let’s assume practical bounds like 0 <= m, n <= 10^4 if not explicitly stated otherwise.
2. Could the matrix be empty?
   • We should handle this edge case and assume an empty matrix returns True because there are no elements to form a conflicting diagonal.

Strategy:

To determine whether the given matrix is a Toeplitz matrix, we need to ensure that each element in the matrix is equal to the element diagonally before it. Specifically, for every element at position (i, j), it must hold that matrix[i][j] == matrix[i-1][j-1] if both i-1 and j-1 are within the matrix bounds.

Pseudocode:

• Traverse through the matrix starting from the second row and the second column.
• For each element at (i, j), check if it is equal to the element at (i-1, j-1).
• If any such comparison fails, return False.
• If no comparison fails, return True.

Code:

def isToeplitzMatrix(matrix):
    if not matrix or not matrix[0]:
        return True

    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

Explanation:

1. Initial Check: We first check if the matrix is empty or if its first row is empty. If so, we return True.
2. Iterate through Elements: We loop through the matrix starting from i=1 and j=1 because the first row and column do not need to be checked.
3. Diagonal Comparison: For each element (i, j), we compare it with its top-left diagonal neighbor (i-1, j-1).
4. Return Result: If any diagonal check fails, we return False. If all checks pass, we return True.

Time Complexity:

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because we are iterating through each element in the matrix once.
• Space Complexity: O(1), since we are only using a constant amount of extra space for our variables.

This algorithm efficiently verifies if the given matrix is Toeplitz by leveraging direct element comparison based on their indices within the bounds of the matrix.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?