Problem Description
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.
Key Insights
- A diagonal in the matrix can be defined by its starting element at (i, j), where i is the row index and j is the column index.
- Elements in the same diagonal will satisfy the condition that their row and column indices differ by the same amount (i.e., i - j is constant).
- We can check each element against the element to its bottom-right (i.e., matrix[i][j] should equal matrix[i + 1][j + 1]).
Space and Time Complexity
Time Complexity: O(m * n)
Space Complexity: O(1)
Solution
To determine if a matrix is Toeplitz, we can iterate through each element of the matrix (except for the last row and last column) and compare it with the element directly below and to the right. If any comparison fails, we return false; if all pass, we return true. This approach uses constant space since we only track the current state, and it runs in linear time relative to the number of elements in the matrix.