Intuitive solution in python (44ms) with explanation


  • 1
    H

    here comes an quite intuitive solution to fill the matrix from 1 to n^2 step by step:

    • define a turple: (directionX, directionY) which indicates the next direction to fill the matrix - think of it as the game: "greedy snake"

    • it's easy to calculate the possible states in order:

      • (0, 1) - direction right (also init state)
      • (1, 0) - direction down
      • (0, -1)- direction left
      • (-1, 0) - direction up
    • only change the direction when we "hit a wall" - say index out of range, or that field has been filled

    • change direction is easy

        def changeDirection(directionX, directionY):
            return directionY, -directionX
      

    python code:

    class Solution(object):
        def generateMatrix(self, n):
            if n == 0: return []
            result = [[None] * n for _ in xrange(n)]
            
            directionX, directionY = 0, 1
            x, y = 0, 0
            for num in xrange(1, n*n+1):
                result[x][y] = num
                if x+directionX >= n or y+directionY >= n or result[x+directionX][y+directionY] is not None:
                    # change direction
                    directionX, directionY = directionY, -directionX
                x += directionX
                y += directionY
            return result

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.