toeplitz-matrix-validator.py

# Store 3 hashes:
#   When `row == 0`, we do not yet know the maximum length of `col`:
#     1. H[0] = 0 or previous H[1] (hash of all values excluding the final one for the column)
#     2. H[1] = hash((H[1], value)) (hash of all values including the final one for the column)
#     3. self.end = col
#   When `row > 0` and `col < self.end`:
#     1. H[1] = hash((H[1], value)) (hash of left-hand values, excluding last)
#     2. H[2] = 0 or hash((H[2], value)) (hash of right-hand values, excluding first)
#   When `col == self.end`:
#     - Compare H[0] with H[2], if they don't match return False
#     - Otherwise, set H[0] = H[1] and reset H[1] and H[2] to 0

class ToeplitzMatrixValidator:
  def __init__(self):
    self.H = [0] * 3
    self.end = 0
  
  def isToeplitz(self, row, col, value):
    if row == 0:
      # we don't yet know the maximum `col` value
      self.end = col
      self.H[0] = self.H[1]
      self.H[1] = hash((self.H[1], value))
    else:
      if col == 0:
        self.H[1] = hash((0, value))
        self.H[2] = 0
      else:
        if col < self.end:
          self.H[1] = hash((self.H[1], value))
        self.H[2] = hash((self.H[2], value))
        if col == self.end:
          if self.H[2] != self.H[0]:
            return False
          self.H[0] = self.H[1]
          self.H[1] = 0
          self.H[2] = 0
    return True

def isToeplitz(arr):
  m = len(arr)
  if m == 0:
    return True
  n = len(arr[0])
  if n == 0:
    return True
  validator = ToeplitzMatrixValidator()
  for row in xrange(m):
    for col in xrange(n):
      if not validator.isToeplitz(row, col, arr[row][col]):
        return False
  return True

if __name__ == '__main__':
  print(isToeplitz([[1,2,3,4],[5,1,2,3],[6,5,1,2]])) # should be True
  print(isToeplitz([[1,2,3,4],[5,1,9,3],[6,5,1,2]])) # should be False