# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + active=""
# 说明：
#     如果从左上到右下的每个对角线都有相同的元素，那么矩阵就是Toeplitz。
#     现在给定一个M×N矩阵，当且仅当矩阵为Toeplitz时返回True。
#
# Example 1:
#     Input:
#         matrix = [
#           [1,2,3,4],
#           [5,1,2,3],
#           [9,5,1,2]
#         ]
# Output: True
#     Explanation:
#         In the above grid, the diagonals are:
#         "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
#         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.
#
# Note:
#     1、matrix will be a 2D array of integers.
#     2、matrix will have a number of rows and columns in range [1, 20].
#     3、matrix[i][j] will be integers in range [0, 99].
#
# -

class Solution:
    def isToeplitzMatrix(self, matrix) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        if rows == 1: return True
        
        seen = set()
        for r in range(rows):
            for c in range(cols):
                val = matrix[r][c]
                if (r, c) in seen:
                    continue
                seen.add((r, c))
                
                for i in range(r+1, rows):
                    if c + 1 < cols:
                        c += 1
                        seen.add((i, c))
                        if matrix[i][c] != val:
                            return False
        return True


mat_ = [
          [1,2,3,4],
          [5,1,2,3],
          [9,5,1,2]
        ]
solution = Solution()
solution.isToeplitzMatrix(mat_)


class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        if n <= 1:
            return True
        
        m = len(matrix[0])
        
        for i in range(m):
            c = i
            r = 0
            v = matrix[r][c]
            while c<m and r<n:                
                if matrix[r][c] != v:
                    return False
                r += 1
                c += 1
        
        for i in range(1,n):
            c = 0
            r = i
            v = matrix[r][c]
            while c<m and r<n:                
                if matrix[r][c] != v:
                    return False
                r += 1
                c += 1
        
        return True

StarcoderdataJupyterScriptsDedupFiltered