LeetCode 59 Spiral Matrix II

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

For example,
Given n = 3,

You should return the following matrix:

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

Difficulty
Medium

Related Problems

[LeetCode 48] Rotate Image

[LeetCode 54] Spiral Matrix

Analysis

This is similar to Problem Spiral Matrix, except this is a square matrix. When n is odd, the most inner ring is only one element.
We can generate the matrix one ring at a time by adding edges top, right, bottom, and left in clockwise order.

Time: O(M*N)
Space: O(1)

1. Cpp solution

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res;
        int left = 0, right = n - 1, bottom = n - 1, top = 0, num = 1;
        while(left < right && top < bottom){
            for(int i = left; i < right; i++){
                res[top][i] = num++;
            }
            for(int i = top; i < bottom; i++){
                res[i][right] = num++;
            }
            for(int i = right; i > left; i--){
                res[bottom][i] = num++;
            }
            for(int i = bottom; i > top; i--){
                res[i][left] = num++;
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        if(n % 2 == 1) {
            res[n/2][n/2] = num;
        }
        return res;
    }
};

2. Go solution

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }
    top, right, bottom, left := 0, n-1, n-1, 0
    num := 1
    for left < right && top < bottom {
        for i := left; i < right; i++ {
            matrix[top][i] = num
            num++
        }

        for i := top; i < bottom; i++ {
            matrix[i][right] = num
            num++
        }

        for i := right; i > left; i-- {
            matrix[bottom][i] = num
            num++
        }

        for i := bottom; i > top; i-- {
            matrix[i][left] = num
            num++
        }
        top++
        bottom--
        left++
        right--
    }

    if n%2 == 1 {
        matrix[n/2][n/2] = num
    }

    return matrix
}

Reference