menu

[LeetCode] 059. Spiral Matrix II

Problem (Medium)

059. Spiral Matrix II

Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

Example:

Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

Approach 1: (My Solution)

Idea

  • Design a function to fill the boarders;
  • Loop the boarders.

Solution

class Solution1:
    def generateMatrix(self, n): 
        """ 
        :type n: int
        :rtype: List[List[int]]
        """
        res = [[None for _ in range(n)] for _ in range(n)]
        start = 1 
        for r in range(n, 0, -2):
            start = self.genCircle(start, res, r, n)
        for row in res:
            print(row)
        return res 

    def genCircle(self, start, res, r, n): 
        for i in range(r):
            res[(n-r)//2][(n-r)//2+i] = start
            start += 1
        for i in range(r-1):
            res[(n-r)//2+1+i][-1-(n-r)//2] = start
            start += 1
        for i in range(r-1):
            res[-1-(n-r)//2][n-(n-r)//2-2-i] = start
            start += 1
        for i in range(r-2):
            res[n-(n-r)//2-2-i][(n-r)//2] = start
            start += 1
        return start

Complexity

  • Time: $O(n^2)$
  • Space: $O(n^2)$

Approach 2: Tricky Solution - Build it inside-out (Beat 100% Python)

Idea

4-9 lines Python solutions

Start with the empty matrix, add the numbers in reverse order until we added the number 1. Always rotate the matrix clockwise and add a top row:

    ||  =>  |9|  =>  |8|      |6 7|      |4 5|      |1 2 3|
                     |9|  =>  |9 8|  =>  |9 6|  =>  |8 9 4|
                                         |8 7|      |7 6 5|

Solution

class Solution2:
    def generateMatrix(self, n): 
        """ 
        :type n: int
        :rtype: List[List[int]]
        """
        res, lo = [[n*n]], n*n 
        while lo > 1:
            lo, hi = lo - len(res), lo
            #print('res:', res)
            res = [[i for i in range(lo, hi)]] + [list(j) for j in zip(*res[::-1])]
        return res

Complexity

  • Time: $O()$?
  • Space: $O(n^2)$

Approach 3: Spiral path (Genius Solution! Beat 100% Python)

Idea

4-9 lines Python solutions Solution 3

Solution

class Solution3:
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        res = [[None for _ in range(n)] for _ in range(n)]
        i, j, di, dj = 0, 0, 0, 1
        for k in range(n*n):
            res[i][j] = k + 1
            if res[(i+di)%n][(j+dj)%n]:
                di, dj = dj, -di
            i += di
            j += dj
            #print('i:', i, 'j:', j, 'di:', di, 'dj:', dj)
        #print(res)
        return res

Complexity

  • Time: $O(n^2)$
  • Space: $O(n^2)$



KF

Comments