Sponsored
Sponsored
This method involves checking each element of the matrix to ensure that it equals the element diagonally ahead of it - that is, for each cell matrix[i][j], it should be equal to matrix[i+1][j+1], provided both indices are within bounds.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(1), since no additional data structures are used.
1#include <vector>
2using namespace std;
3
4bool isToeplitzMatrix(vector<vector<int>>& matrix) {
5 int rows = matrix.size();
6 int cols = matrix[0].size();
7 for (int i = 0; i < rows - 1; ++i) {
8 for (int j = 0; j < cols - 1; ++j) {
9 if (matrix[i][j] != matrix[i + 1][j + 1]) {
10 return false;
11 }
12 }
13 }
14 return true;
15}In C++, we use std::vector to handle the matrix. A similar logic applies as in C, using nested loops to check diagonal consistency.
We can use a HashMap (or dictionary) to maintain the first element of each diagonal. Each key represents the difference between row and column indices, and the value is the first element at this diagonal. While iterating, if a new element violates this rule, the matrix isn't Toeplitz.
Time Complexity: O(m * n)
Space Complexity: O(m + n) for storing diagonal mappings.
1def isToeplitzMatrix(matrix):
2 diagonal_map = In this Python implementation, a dictionary keeps track of each diagonal. The key (i - j) refers to a specific diagonal, and its value is the element that should be the same for all elements in this diagonal.