/**
 * @author Chaos
 * 766. 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:
 * 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.
 *
 *
 * Solution here is directly check the first line and then check first row.
 * O(M*N)
 */

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;

        if (m == 1||n == 1){
            return true;
        }
        for (int i=0; i< n-1; i++){
            int x=0;
            int y=i;
            while (x+1 < m && y+1 < n){
                if (matrix[x][y]!=matrix[++x][++y])
                    return false;
            }
        }

        for(int j=0; j<m-1; j++){
            int x=j;
            int y=0;
            while (x+1 < m && y+1 < n){
                if (matrix[x][y]!=matrix[++x][++y])
                    return false;
            }
        }
        return true;
    }
}