Leetcode – Toeplitz Matrix Solution in Python

Spread the love

Matrix problems in the programming world present a unique challenge that often demands a deep understanding of both algorithms and the underlying mathematical concepts. One such intriguing problem is determining whether a given matrix is a Toeplitz matrix. Found on LeetCode, the Toeplitz matrix problem is a captivating combination of array traversal and pattern recognition.

In this exhaustive guide, we will delve into the Toeplitz matrix problem, break down its requirements, and explore a Pythonic solution.

Problem Statement

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Given an m x n matrix, return True if and only if the matrix is Toeplitz.

Example

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]".
All the diagonals have the same elements, so the answer is True.

Solution Approaches

Brute Force Approach

The brute force approach involves examining each diagonal in the matrix and ensuring all its elements are the same.

  1. Start with the first column and move row-wise to check diagonals.
  2. Repeat the process for each column.

This approach requires O(m * n) space for an m x n matrix as we might end up storing each diagonal’s values in a separate list to verify the Toeplitz property. The time complexity can be quite high as well, at O(m * n^2).

Optimal Approach

A more efficient method is to check only adjacent rows. For a matrix to be Toeplitz, every element at [i, j] should be the same as the element at [i+1, j+1] for every row and column index i, j.

This insight reduces the problem to simple array traversal, removing the need to store diagonals in separate lists. This approach’s time complexity is O(m * n), and the space complexity is O(1).

Python Solution

Using the optimal approach, we can craft the following Python solution:

def isToeplitzMatrix(matrix):
    for i in range(len(matrix) - 1):  # We don't need to check the last row
        for j in range(len(matrix[0]) - 1):  # We don't need to check the last column
            if matrix[i][j] != matrix[i + 1][j + 1]:
                return False
    return True

# Example Usage
matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
print(isToeplitzMatrix(matrix))  # Expected output: True

Complexities and Conclusion

Time Complexity

For an m x n matrix, the time complexity of the solution is O(m * n) since we have two nested loops traversing the matrix.

Space Complexity

The space complexity is O(1) as we only use a constant amount of space beyond the input matrix.

Conclusion

The Toeplitz matrix problem is an excellent example of how observing the inherent patterns in the problem statement can lead to a significant reduction in solution complexity. While the brute force method is intuitive, the optimal approach demonstrates the importance of fully understanding the problem’s constraints and properties.

Leave a Reply