59. Spiral Matrix II

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

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

Very similar to Spiral matrix 1

    def generateMatrix(self, n: 'int') -> 'List[List[int]]':
        c_start = 0
        c_end = n - 1
        r_start = 0
        r_end = n - 1
        res = [ [1 for i in range(n)] for i in range(n) ]
        ctr = 1
        while r_start <= r_end and c_start <= c_end:
            for i in range(c_start, c_end + 1):
                res[r_start][i] = ctr 
                ctr += 1
            for i in range(r_start + 1, r_end + 1):
                res[i][c_end] = ctr
                ctr += 1
            for i in range(c_end - 1, c_start, -1):
                res[r_end][i] = ctr
                ctr += 1
            for i in range(r_end, r_start, - 1):
                res[i][c_start] = ctr
                ctr += 1

            c_start += 1
            c_end -= 1
            r_start += 1
            r_end -= 1

Watch out

Partition of matrix

We partition the outmost layer of matrix into n ( the top horizontal), two n – 1( two vertical) and one n – 2 group ( the bottom horizontal).

EG

1 2 3 
8 9 4
7 6 5

123 belongs to the first group, 4,5 and 8,7 belong to the vertical group, and 6 belong to the bottom horizontal group.
This partition has one advantage: It deals with the edge case when the matrix is a singleton.
In that case, all group but the first group is empty.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax