766. Toeplitz Matrix


Problem Description

Given an m x n matrix, the task is to determine if the matrix is a Toeplitz matrix. A matrix is considered Toeplitz if every diagonal from the top-left to the bottom-right corners has the same elements. This means that if you pick any element and look at the elements diagonally down and to the right, all those elements should be identical. This must hold true for all the elements in the matrix, except for those on the last row and the rightmost column since they do not have any diagonal elements.

To conceptualize this, imagine a 3x3 matrix as an example:

1a, b, c
2d, a, b
3e, d, a

This is a Toeplitz matrix because the diagonals ((a, a, a), (b, b), and (c), along with (d, d) and (e)) from the top-left to the bottom right consist of the same elements.

The problem requires a function that takes such a matrix as input and returns true if the matrix is Toeplitz, and false otherwise.

Intuition

To check if a matrix is Toeplitz, we only need to verify that each element is equal to the one directly diagonally up and to the left of it. This is because if each element has this property, then by transitivity, all elements on the diagonal will be equivalent.

We start checking from the second row and the second column since the elements in the first row and the first column don't have any diagonal predecessors.

The idea is to iterate through the matrix while comparing each element (i, j) with the element (i - 1, j - 1). If all such pairs of elements are equal, we can conclude that the matrix is Toeplitz. Otherwise, if we find any pair of elements that do not match, we immediately know the matrix is not Toeplitz, and we can return false.

The solution provided uses the all() function with a generator expression to perform this check. The generator goes through all elements of the matrix starting from the second row and second column, and the all() function tests whether every element [i][j] equals the element [i - 1][j - 1]. If all pairs are equal, it returns true, otherwise false. This approach is concise and efficient because it only goes through the necessary elements once and does not check the entire matrix.

Solution Approach

The solution uses a simple iteration pattern to walk through the elements of the matrix and a logical test to validate the Toeplitz condition.

Implementation Details:

  1. Data Structures: The primary data structure used is the input matrix itself, which is a 2D list, denoted as matrix.
  2. Variables: Two variables m and n are used to store the dimensions of the matrix.
  3. For Loops: Two nested for loops are constructed, where i ranges from 1 to m - 1 and j ranges from 1 to n - 1. This makes sure we're starting from the second row and column.
  4. Comparison: Inside the loops, we compare each element matrix[i][j] with the element matrix[i - 1][j - 1]. This is done with a simple equality check: matrix[i][j] == matrix[i - 1][j - 1].
  5. Generator Expression: This comparison is encapsulated within a generator expression which efficiently creates an iterator for each element's comparison and for loop iteration.
  6. all() Function: The generator expression is fed into Python's built-in all() function. The all() function is perfect for this scenario because it requires all values from the iterator to be True for the entire expression to evaluate as True. If there is even one False, it returns False. This aligns exactly with our requirement: all comparisons must be True for the matrix to be Toeplitz.

The return all(...) line in the code is where the entire logic is applied. It checks all the pairs (continuing until either end of the matrix is reached) and confirms if every required element satisfies the Toeplitz condition. This one-liner leverages Python's readability and built-in functions to implement an elegant and scalable solution.

The code elegantly handles the problem with a high level of efficiency, as it stops checking as soon as one pair of elements fails the test, due to the lazy evaluation property of the generator expression used in the all() function. This means that the function will have early termination and will not perform unnecessary checks once a non-Toeplitz pair is found.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

To illustrate the solution approach, let's consider a small 3x3 matrix:

11, 2, 3
24, 1, 2
35, 4, 1

We are tasked with determining if this is a Toeplitz matrix.

  1. Initialization: According to our solution approach, we need the dimensions of the matrix. For this 3x3 matrix, m is 3 (number of rows) and n is 3 (number of columns).

  2. Iteration: We set up two nested for loops. The outer loop iterates over i from 1 to 2 (m - 1), which corresponds to the second and third rows. The inner loop iterates over j from 1 to 2 (n - 1), covering the second and third columns.

  3. Comparison and Early Termination: We compare the elements starting at matrix[1][1]:

    • For i = 1, j = 1: We check if matrix[1][1] is equal to matrix[0][0]. For our matrix, it checks if 1 equals 1, which is true.
    • For i = 1, j = 2: We check if matrix[1][2] is equal to matrix[0][1]. It checks if 2 equals 2, which is true.
    • For i = 2, j = 1: We check if matrix[2][1] is equal to matrix[1][0]. It checks if 4 equals 4, which is true.
    • For i = 2, j = 2: We check if matrix[2][2] is equal to matrix[1][1]. It checks if 1 equals 1, which is true.

All comparisons are true, which means each pair of compared elements satisfies the Toeplitz condition.

  1. Generator Expression and all() Function: The generator expression is as follows:

    1(matrix[i][j] == matrix[i - 1][j - 1] for i in range(1, m) for j in range(1, n))

    In our case, this generator will create an iterator (True, True, True, True) from the above comparisons.

    The all() function takes this iterator as an input and returns True because all elements are True. If there was any False in the iterator, all() would return False, indicating the matrix is not Toeplitz.

Therefore, for this given 3x3 matrix, the function concludes with True, confirming that it is indeed a Toeplitz matrix.

Solution Implementation

1from typing import List
2
3class Solution:
4    def is_toeplitz_matrix(self, matrix: List[List[int]]) -> bool:
5        """
6        Check if a matrix is a Toeplitz matrix.
7        A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
8
9        :param matrix: 2D List[int], the input matrix to check
10        :return: bool, True if the matrix is Toeplitz, False otherwise
11        """
12
13        # Number of rows in the matrix
14        row_count = len(matrix)
15        # Number of columns in the matrix
16        col_count = len(matrix[0])
17
18        # Iterate over each element in the matrix starting from the second row and second column
19        # because the comparison starts with the element just above and to the left (i-1, j-1).
20        for i in range(1, row_count):
21            for j in range(1, col_count):
22                # Compare the current element with the element diagonally above and to the left.
23                # If any such comparison fails, the matrix is not Toeplitz.
24                if matrix[i][j] != matrix[i - 1][j - 1]:
25                    return False
26
27        # If all diagonal comparisons hold, the matrix is Toeplitz.
28        return True
29
1class Solution {
2    /**
3     * Checks if a given matrix is a Toeplitz matrix.
4     * A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
5     *
6     * @param matrix The input matrix to check.
7     * @return true if the matrix is Toeplitz; otherwise, false.
8     */
9    public boolean isToeplitzMatrix(int[][] matrix) {
10        // m is the number of rows in the matrix
11        int numRows = matrix.length;
12        // n is the number of columns in the matrix
13        int numCols = matrix[0].length;
14      
15        // Start from the second row and column because we will be comparing with the element above and to the left
16        for (int i = 1; i < numRows; ++i) {
17            for (int j = 1; j < numCols; ++j) {
18                // If the current element is not the same as the one above and to the left, return false
19                if (matrix[i][j] != matrix[i - 1][j - 1]) {
20                    return false;
21                }
22            }
23        }
24      
25        // If all diagonals from top-left to bottom-right have the same elements, return true
26        return true;
27    }
28}
29
1#include <vector>
2
3// Class to define the solution.
4class Solution {
5public:
6    // Function to check whether a given matrix is a Toeplitz matrix.
7    // A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
8    // @param matrix: 2D vector of ints representing the input matrix.
9    // @return: boolean value indicating whether the matrix is Toeplitz.
10    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
11        // Get the number of rows in the matrix.
12        int numRows = matrix.size();
13        // Get the number of columns in the matrix.
14        int numCols = matrix[0].size();
15
16        // Start from the second row and second column as the first row and column 
17        // do not have a top-left element to be compared with.
18        for (int row = 1; row < numRows; ++row) {
19            for (int col = 1; col < numCols; ++col) {
20                // Compare the current element with the top-left neighbor.
21                // If they are not the same, the matrix is not Toeplitz, return false.
22                if (matrix[row][col] != matrix[row - 1][col - 1]) {
23                    return false;
24                }
25            }
26        }
27
28        // If no discrepancies are found, return true indicating it is a Toeplitz matrix.
29        return true;
30    }
31};
32
1/**
2 * Function to check if a matrix is a Toeplitz matrix.
3 * A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
4 * @param matrix A 2D array of numbers representing the matrix.
5 * @returns true if the matrix is Toeplitz, otherwise false.
6 */
7function isToeplitzMatrix(matrix: number[][]): boolean {
8    // Get the number of rows in the matrix
9    const rowCount: number = matrix.length;
10    // Get the number of columns in the matrix by checking the first row
11    const columnCount: number = matrix[0].length;
12
13    // Start from the first row (skipping the first element) and check all diagonals
14    for (let rowIndex = 1; rowIndex < rowCount; ++rowIndex) {
15        for (let columnIndex = 1; columnIndex < columnCount; ++columnIndex) {
16            // If the current element is not equal to the element in the previous row and previous column,
17            // it's not a Toeplitz matrix
18            if (matrix[rowIndex][columnIndex] !== matrix[rowIndex - 1][columnIndex - 1]) {
19                return false;
20            }
21        }
22    }
23
24    // If all diagonals have the same elements, return true
25    return true;
26}
27
28// Example usage:
29// const matrix: number[][] = [
30//     [1, 2, 3, 4],
31//     [5, 1, 2, 3],
32//     [9, 5, 1, 2]
33// ];
34// console.log(isToeplitzMatrix(matrix)); // Should log true
35

Time and Space Complexity

The time complexity of the given code is O(m * n) where m is the number of rows in the matrix and n is the number of columns. This is because the code iterates through each element in the matrix, starting from the second row and the second column, checking the top-left diagonal element for each cell.

The space complexity of the code is O(1) meaning it does not allocate any additional space that scales with the input size. The use of variables m and n and the iterative checks on the matrix elements do not require additional space beyond the input itself.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄