algoadvance

Leetcode 766. Toeplitz Matrix

Problem Statement

Given an m x n matrix, return true if the matrix is a Toeplitz Matrix. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

Clarifying Questions

1. What should be returned if the matrix is empty?
   • Since the definition isn’t applicable, we would return true by convention.
2. Should the matrix contain any specific types of elements?
   • No, it can contain any integer values.
3. What if the matrix is a single row or a single column?
   • It would still be considered Toeplitz as there are no diagonals to compare.

Strategy

1. Iterate over each element in the matrix (excluding the last row and column).
2. For each element at position (i,j), compare it with the element at position (i+1, j+1).
3. If any pair of elements are not equal, return false.
4. If all comparisons are valid, return true.

Code

Here’s a possible implementation in C++:

#include <vector>

using namespace std;

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        for (int i = 0; i < m - 1; ++i) {
            for (int j = 0; j < n - 1; ++j) {
                if (matrix[i][j] != matrix[i+1][j+1]) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

Time Complexity

• The time complexity of this solution is (O(m \times n)), where m is the number of rows and n is the number of columns. This is because every element (excluding the last row and column) is checked once.
• The space complexity is (O(1)) because we do not use any additional space proportional to the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?