We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Toeplitz Matrix

Number: 777

Difficulty: Easy

Paid? No

Companies: Meta, Google, tcs

Problem Description

Given an m x n matrix, determine if the matrix is Toeplitz – that is, every diagonal from top-left to bottom-right has all the same elements. Return true if it is a Toeplitz matrix; otherwise, return false.

Key Insights

  • Each element (except those in the first row and first column) must be equal to its top-left neighbor.
  • You can validate the matrix by iterating from the second row/column and comparing each element with matrix[i-1][j-1].
  • This simple check allows you to determine if every diagonal has the same elements without extra space.
  • For streaming data (loading one row at a time), maintain the previous row for comparison.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Solution

The problem is solved by iterating through the matrix starting from the element at position (1, 1). For every element at matrix[i][j], compare it with the element at matrix[i-1][j-1]. If any two elements in this pair do not match, the matrix is not Toeplitz. This check ensures that every diagonal from the top-left to bottom-right has identical elements. In terms of auxiliary space, only constant extra space is used, which makes this approach efficient both in time and space.

Code Solutions

# Function to determine if the matrix is Toeplitz
def isToeplitzMatrix(matrix):
    # Get the number of rows and columns in the matrix
    rows = len(matrix)
    cols = len(matrix[0])
    
    # Iterate starting from row 1 and column 1 because first row and column are trivially Toeplitz
    for i in range(1, rows):
        for j in range(1, cols):
            # Compare current element with its top-left neighbor
            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]]
print(isToeplitzMatrix(matrix1))  # Expected output: True
← Back to All Questions