Python Easy To Understand O(n^2)


#1

class Solution:
# @param A : integer
# @return a list of list of integers

def isValid(self, mat, i, j):
    # is valid indexes
    return i >= 0 and j >= 0 and i < len(mat) and j < len(mat) and mat[i][j] == 0

def isFinish(self, mat, i, j):
    # can't move to any direction (four O(1) checks)
    return not self.isValid(mat, i + 1, j) and not self.isValid(mat, i - 1, j) and not self.isValid(mat, i,j + 1) and not self.isValid(mat, i, j - 1)

def generateMatrix(self, A):
    mat = [[0] * A for i in range(A)]
    mat[0][0]=1
    i = j = 0
    curr = 2
    direction = 0
    while not self.isFinish(mat, i, j):

        iprev, jprev = i, j

        if direction == 0:
            j += 1
        elif direction == 1:
            i += 1
        elif direction == 2:
            j -= 1
        else:
            i -= 1

        if self.isValid(mat, i, j):
            mat[i][j] = curr
            curr += 1
        else:
            i, j = iprev, jprev
            direction = (direction + 1) % 4
            
    return mat