Toeplitz Matrix

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: True Explanation: 1234 5123 9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True. Example 2:

Input: matrix = [[1,2],[2,2]] Output: False Explanation: The diagonal "[1, 2]" has different elements.

Solution: Check the first row and first column

The idea is very simple. For each element of first row and first column(or last row and last column) in the matrix, we check if descending diagonal starting from that element have same values or not. If we found any diagonal having different values, we return false.

bool checkDiagonal(vector<vector<int>>& matrix, int i, int j) {
    int row = matrix.size();
    int col = matrix[0].size();

    int res = matrix[i][j];
    while(i < row && j < col) {
        if(matrix[i][j] != res) return false;
        i += 1;
        j += 1;
    }

    return true;
}

bool isToeplitzMatrix(vector<vector<int>>& matrix) {
    // Check the first row 
    for(int c=0; c<matrix[0].size(); c++) {
        if(!checkDiagonal(matrix, 0, c)) return false;
    }

    // Check the first column
    for(int r=0; r<matrix.size(); r++) {
        if(!checkDiagonal(matrix, r, 0)) return false;
    }

    return true;
}