Construct a Spiral Matrix using Simulation Algorithm

Given a 2-d array matrix, return elements in spiral order starting from matrix[0][0].

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input

matrix = [
    [6, 9, 8],
    [1, 8, 0],
    [5, 1, 2],
    [8, 0, 3],
    [1, 6, 4],
    [8, 8, 10]
]

Output

[6, 9, 8, 0, 2, 3, 4, 10, 8, 8, 1, 8, 5, 1, 8, 1, 0, 6]

Simulation Algorithm to Build a Spiral Matrix

The initial direction is right. We simulate walking to it until we are about to go outside the boundary or visit a pixel that has been visited before. Then, it is the time to turn 90 degree. We can store the direction offsets in a vector array.

vector<int> spiralMatrix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (0 == rows) return {};
    int cols = matrix[0].size();
    if (0 == cols) return {};
    vector<int> ans;    
    int r = 0, c = 0, n = rows * cols - 1;
    bool vis[rows][cols];
    memset(vis, false, sizeof vis);
    vector<vector<int>> dir({{0, 1}, {1, 0}, {0, -1}, {-1, 0}});
    int di = 0;
    for (; n > 0; -- n) {
        ans.push_back(matrix[r][c]);
        vis[r][c] = true;                
        for (;;) {
            auto d = dir[di];
            int nr = r + d[0];
            int nc = c + d[1];
            if ((nr >= 0) && (nc >= 0) && (nr < rows) && (nc < cols) && (!vis[nr][nc])) { // continue same direction
                r = nr;
                c = nc;
                break;
            } else { // need to turn 90 clockwise
                di = (di + 1) % 4;
            }
        }
    }
    ans.push_back(matrix[r][c]);
    return ans;
}

We use a two dimensional boolean array to mark if a pixel that has been visited. The following uses a single direction vector {0, 1, 0, -1, 0} that index (x, x+1) is the 2D dimension direction offset.

vector<int> spiralMatrix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (0 == rows) return {};
    int cols = matrix[0].size();
    if (0 == cols) return {};
    vector<int> ans;    
    int r = 0, c = 0, n = rows * cols - 1;
    bool vis[rows][cols];
    memset(vis, false, sizeof vis);
    vector<int> dir{0, 1, 0, -1, 0};
    int di = 0;
    for (; n > 0; -- n) {
        ans.push_back(matrix[r][c]);
        vis[r][c] = true;                
        for (;;) {
            int nr = r + dir[di];
            int nc = c + dir[di + 1];
            if ((nr >= 0) && (nc >= 0) && (nr < rows) && (nc < cols) && (!vis[nr][nc])) {
                r = nr;
                c = nc;
                break;
            } else {
                di = (di + 1) % 4;
            }
        }
    }
    ans.push_back(matrix[r][c]);
    return ans;
}

Both implementations take O(RC) time to finish and O(RC) space complexity – where R and C are the number of the rows, and the number of columns respectively.

See also: Algorithm to Generate the Spiral Matrix in Clock-wise Order

–EOF (The Ultimate Computing & Technology Blog) —