1
###########################################################################################
2
#   Runtime: O(MN)
3
#       Number of rows(M) x expected numbers(N)
4
#   Space: O(N)
5
#       We need to store the expected numbers in list
6
############################################################################################
7
class Solution:
8
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
9
        # Validate Input
10
        if not matrix or not matrix[0]:
11
            return False
12

13
        # Create a deque tracking the expected values for the next row
14
        expected = matrix[0]
15
        # We only care about the elements before last element
16
        expected.pop()
17

18
        # From the second row, pop out the last element of the expected numbers and compare it with the target row[1:]
19
        for row in matrix[1:]:
20
            # Compare row with expected numbers, invalidate it as soon as we find the numbers are not the same (O(N))
21
            if row[1:] != expected:
22
                return False
23
            else:
24
                # Pop the last element from row, use it as the expected numbers for the next iteration
25
                row.pop()
26
                expected = row
27
        # If we've reached here, all diagonals aligned
28
        return True