Jobs

Interviews

Discussions

Toeplitz Matrix

#945 Most AskedEasy

Toeplitz Matrix #945 Most Asked

Easy

Google

6 views

Topics:

Arrays

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?

Try coding it in LeetCode

Toeplitz Matrix

#945 Most AskedEasy

Toeplitz Matrix #945 Most Asked

Easy

Google

6 views

Topics:

Arrays

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?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the matrix?
Can the matrix be empty, or can it have zero rows or zero columns?
Is the input always a rectangular matrix, or could it be jagged?
Are all the elements integers, or could they be other data types like floats?
By 'Toeplitz Matrix,' do we strictly require that every diagonal from top-left to bottom-right has the same element, or is a near-Toeplitz matrix acceptable?

Brute Force Solution

Approach

The problem asks us to check if a given grid of numbers is a special type of matrix called a Toeplitz matrix. To do this the brute force method will compare every number to a specific other number in the grid.

Here's how the algorithm would work step-by-step:

Pick a number in the grid along the top row.
Look at the number diagonally down and to the right from it.
Check if these two numbers are the same.
If they are not, then the grid cannot be a Toeplitz matrix.
Repeat this process, checking each number with its diagonal neighbor, starting from the top row until reaching the end of the grid.
Now, pick a number in the grid from the first column, skipping the top-left corner number since those diagonals were already tested.
Look at the number diagonally down and to the right from it.
Check if these two numbers are the same.
If they are not, then the grid cannot be a Toeplitz matrix.
Repeat this process, checking each number with its diagonal neighbor, starting from the first column, until reaching the end of the grid.
If all the numbers match along the diagonals, we can then say the matrix is a Toeplitz matrix.

Code Implementation

def is_toeplitz_matrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for column_start_index in range(number_of_columns):
        # Check diagonals starting from the top row
        value_to_compare = matrix[0][column_start_index]

        row_index = 1
        column_index = column_start_index + 1

        while row_index < number_of_rows and column_index < number_of_columns:
            if matrix[row_index][column_index] != value_to_compare:
                return False

            row_index += 1
            column_index += 1

    # Skip the top-left since those diagonals were already tested
    for row_start_index in range(1, number_of_rows):
        value_to_compare = matrix[row_start_index][0]

        row_index = row_start_index + 1
        column_index = 1

        # Check diagonals starting from the first column
        while row_index < number_of_rows and column_index < number_of_columns:
            if matrix[row_index][column_index] != value_to_compare:
                return False

            row_index += 1
            column_index += 1

    return True

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each row and column of the matrix to verify the Toeplitz property. In the worst-case scenario, every element in the matrix needs to be checked against its diagonal neighbor. Therefore, if 'm' represents the number of rows and 'n' represents the number of columns, the algorithm performs a comparison for nearly every element once. This yields a time complexity proportional to the total number of elements in the matrix, which is m * n, thus O(m*n).

Space Complexity

O(1) – The algorithm iterates through the matrix, comparing elements along diagonals, but it doesn't use any auxiliary data structures to store intermediate results or track visited cells. It only uses a few constant-size variables for indices or comparisons. The space used by these variables is independent of the size of the input matrix (number of rows and columns). Therefore, the space complexity is constant.

Optimal Solution

Approach

The key is to realize that in a Toeplitz matrix, all diagonals have the same value. So, to check if a matrix is Toeplitz, we only need to compare each element to the element diagonally above and to the left of it.

Here's how the algorithm would work step-by-step:

Start at the second row and second column of the matrix.
For each element, compare it to the element that's one row above and one column to the left.
If the current element is different from the element diagonally above and to the left, the matrix is not Toeplitz, and you can stop checking.
If you reach the end of the matrix without finding any mismatches, the matrix is a Toeplitz matrix.

Code Implementation

def is_toeplitz_matrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Start from the second row and second column.
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            # Compare with the element diagonally above and to the left.
            if matrix[row_index][column_index] != matrix[row_index - 1][column_index - 1]:

                # If elements do not match, it's not a Toeplitz matrix.
                return False

    # If all elements match, it's a Toeplitz matrix.
    return True

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through the matrix starting from the second row and second column. The outer loop implicitly goes through each row (there are 'm' rows) and the inner loop goes through each column (there are 'n' columns). For each element matrix[i][j], a single comparison is made. Therefore, the total number of operations is proportional to m * n, where m is the number of rows and n is the number of columns, resulting in a time complexity of O(m * n).

Space Complexity

O(1) – The provided algorithm only uses a few constant space variables for looping and comparison. It does not create any auxiliary data structures that scale with the input matrix size. Therefore, the space complexity is constant, regardless of the number of rows or columns in the matrix. The extra memory required remains the same for any input size.

Edge Cases

Case	How to Handle
Null or empty matrix	Return true immediately as an empty matrix trivially satisfies the Toeplitz property.
1x1 matrix	Return true, as a single element matrix trivially satisfies the condition.
Matrix with only one row or one column	Return true because only one diagonal exists and all elements on it are equal.
Large matrix (performance considerations)	Ensure the solution iterates efficiently to avoid exceeding time limits for large inputs, and potentially consider using generators to reduce memory footprint.
Matrix with all elements the same	The algorithm will correctly identify this as a Toeplitz matrix.
Integer overflow if elements are very large	The solution should not involve calculations that could lead to an integer overflow; comparison should be safe.
Matrix with negative numbers, zeros, and positive numbers	The algorithm should handle all number types correctly through direct comparison.
Non-square Toeplitz matrices	The algorithm should correctly verify if the matrix is Toeplitz even if the number of rows and columns are different.

Null or empty matrix

How to Handle:

Return true immediately as an empty matrix trivially satisfies the Toeplitz property.

1x1 matrix

How to Handle:

Return true, as a single element matrix trivially satisfies the condition.

Matrix with only one row or one column

How to Handle:

Return true because only one diagonal exists and all elements on it are equal.

Large matrix (performance considerations)

How to Handle:

Ensure the solution iterates efficiently to avoid exceeding time limits for large inputs, and potentially consider using generators to reduce memory footprint.

Matrix with all elements the same

How to Handle:

The algorithm will correctly identify this as a Toeplitz matrix.

Integer overflow if elements are very large

How to Handle:

The solution should not involve calculations that could lead to an integer overflow; comparison should be safe.

Matrix with negative numbers, zeros, and positive numbers

How to Handle:

The algorithm should handle all number types correctly through direct comparison.

Non-square Toeplitz matrices

How to Handle:

The algorithm should correctly verify if the matrix is Toeplitz even if the number of rows and columns are different.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the matrix?
Can the matrix be empty, or can it have zero rows or zero columns?
Is the input always a rectangular matrix, or could it be jagged?
Are all the elements integers, or could they be other data types like floats?
By 'Toeplitz Matrix,' do we strictly require that every diagonal from top-left to bottom-right has the same element, or is a near-Toeplitz matrix acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick a number in the grid along the top row.
Look at the number diagonally down and to the right from it.
Check if these two numbers are the same.
If they are not, then the grid cannot be a Toeplitz matrix.
Repeat this process, checking each number with its diagonal neighbor, starting from the top row until reaching the end of the grid.
Now, pick a number in the grid from the first column, skipping the top-left corner number since those diagonals were already tested.
Look at the number diagonally down and to the right from it.
Check if these two numbers are the same.
If they are not, then the grid cannot be a Toeplitz matrix.
Repeat this process, checking each number with its diagonal neighbor, starting from the first column, until reaching the end of the grid.
If all the numbers match along the diagonals, we can then say the matrix is a Toeplitz matrix.

Code Implementation

def is_toeplitz_matrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for column_start_index in range(number_of_columns):
        # Check diagonals starting from the top row
        value_to_compare = matrix[0][column_start_index]

        row_index = 1
        column_index = column_start_index + 1

        while row_index < number_of_rows and column_index < number_of_columns:
            if matrix[row_index][column_index] != value_to_compare:
                return False

            row_index += 1
            column_index += 1

    # Skip the top-left since those diagonals were already tested
    for row_start_index in range(1, number_of_rows):
        value_to_compare = matrix[row_start_index][0]

        row_index = row_start_index + 1
        column_index = 1

        # Check diagonals starting from the first column
        while row_index < number_of_rows and column_index < number_of_columns:
            if matrix[row_index][column_index] != value_to_compare:
                return False

            row_index += 1
            column_index += 1

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the second row and second column of the matrix.
For each element, compare it to the element that's one row above and one column to the left.
If the current element is different from the element diagonally above and to the left, the matrix is not Toeplitz, and you can stop checking.
If you reach the end of the matrix without finding any mismatches, the matrix is a Toeplitz matrix.

Code Implementation

def is_toeplitz_matrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Start from the second row and second column.
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            # Compare with the element diagonally above and to the left.
            if matrix[row_index][column_index] != matrix[row_index - 1][column_index - 1]:

                # If elements do not match, it's not a Toeplitz matrix.
                return False

    # If all elements match, it's a Toeplitz matrix.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return true immediately as an empty matrix trivially satisfies the Toeplitz property.
1x1 matrix	Return true, as a single element matrix trivially satisfies the condition.
Matrix with only one row or one column	Return true because only one diagonal exists and all elements on it are equal.
Large matrix (performance considerations)	Ensure the solution iterates efficiently to avoid exceeding time limits for large inputs, and potentially consider using generators to reduce memory footprint.
Matrix with all elements the same	The algorithm will correctly identify this as a Toeplitz matrix.
Integer overflow if elements are very large	The solution should not involve calculations that could lead to an integer overflow; comparison should be safe.
Matrix with negative numbers, zeros, and positive numbers	The algorithm should handle all number types correctly through direct comparison.
Non-square Toeplitz matrices	The algorithm should correctly verify if the matrix is Toeplitz even if the number of rows and columns are different.

Null or empty matrix

How to Handle:

Return true immediately as an empty matrix trivially satisfies the Toeplitz property.

1x1 matrix

How to Handle:

Return true, as a single element matrix trivially satisfies the condition.

Matrix with only one row or one column

How to Handle:

Return true because only one diagonal exists and all elements on it are equal.

Large matrix (performance considerations)

How to Handle:

Ensure the solution iterates efficiently to avoid exceeding time limits for large inputs, and potentially consider using generators to reduce memory footprint.

Matrix with all elements the same

How to Handle:

The algorithm will correctly identify this as a Toeplitz matrix.

Integer overflow if elements are very large

How to Handle:

The solution should not involve calculations that could lead to an integer overflow; comparison should be safe.

Matrix with negative numbers, zeros, and positive numbers

How to Handle:

The algorithm should handle all number types correctly through direct comparison.

Non-square Toeplitz matrices

How to Handle:

The algorithm should correctly verify if the matrix is Toeplitz even if the number of rows and columns are different.

0/1916 Google questions completed

0/1916 completed