Problem Statement

You are given an m x n matrix. A matrix is Toeplitz if every diagonal from the top-left to the bottom-right has the same elements.

You need to return true if the matrix is Toeplitz, otherwise return false.

Examples

Example 1:

Input: matrix = [
                 [1, 2, 3, 4],
                 [5, 1, 2, 3],
                 [9, 5, 1, 2]
                ]
Output: true

Explanation:
In this matrix, every diagonal from top-left to bottom-right has the same element:
Diagonal starting at (0, 0): 1, 1, 1
Diagonal starting at (0, 1): 2, 2, 2
Diagonal starting at (0, 2): 3, 3
Diagonal starting at (0, 3): 4
Diagonal starting at (1, 0): 5, 5
Diagonal starting at (2, 0): 9

Example 2:

Input: matrix = [
                 [1, 2],
                 [2, 2]
                ]
Output: false

Explanation:
The diagonal starting at (0, 0) contains 1, 2 which are different, so the
matrix is not Toeplitz.

Different Approaches

1️⃣ Brute Force Iterative Approach

Intuition:

To check whether the matrix is Toeplitz, we need to ensure that every diagonal has the same elements. This means that for every element matrix[i][j], it should be equal to matrix[i+1][j+1] if they are both within bounds.

Steps:

1. Traverse the matrix element by element, except the last row and the last column.
2. For each element matrix[i][j], check if matrix[i][j] == matrix[i+1][j+1].
3. If any such check fails, return false.
4. If no check fails, return true.

Code:

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        // Check all elements except the last row and last column
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                // If the current element is not equal to the element on the diagonal, return false
                if (matrix[i][j] != matrix[i+1][j+1]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
• Space Complexity: O(1)

2️⃣ Hash Map by Diagonal

Intuition:

Each diagonal in the matrix can be identified by the difference between its row and column indices, i.e., for any element matrix[i][j], the diagonal it belongs to is identified by i - j. If we store the first element we encounter for each diagonal, we can check if all other elements in that diagonal are equal.

Steps:

1. Use a hash map to store the first element encountered for each diagonal, where the key is i - j.
2. Traverse the matrix, and for each element matrix[i][j], check if it matches the value stored in the hash map for the corresponding diagonal i - j.
3. If any mismatch occurs, return false.
4. If no mismatches occur, return true.

Code:

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        unordered_map<int, int> diagonal_map;
        
        int m = matrix.size();
        int n = matrix[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // The key for each diagonal is i - j
                if (diagonal_map.find(i - j) == diagonal_map.end()) {
                    // If this diagonal has not been seen yet, store its first value
                    diagonal_map[i - j] = matrix[i][j];
                } else if (diagonal_map[i - j] != matrix[i][j]) {
                    // If the current value does not match the stored value, return false
                    return false;
                }
            }
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(m * n), where m is the number of columns, and n is the number of rows.
• Space Complexity: O(m + n)
  • We use a hash map to store the values of the diagonals, which has a space complexity of O(m+n) (since there can be at most m + n - 1 diagonals).