LeetCode Spiral Matrix I and II: Recursive and Iterative Index Calculation

Overview

LeetCode Spiral Matrix I and II is to test array index manipulation which can be done in both recursive and iterative manner to find the pattern of calculation

LeetCode Spiral Matrix I and II

(1)

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

(2)

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 ]
]

Analysis: Recursive and Iterative Index Calculation

Basically, this problem could be solved by bother recursive and iterative algorithm, just directly simulate the spiral pattern: top->right->bottom->left. And the following recursive implementation for Spiral Matrix I is accepted by LeetCode OJ:

class Solution {
    public:
        vector<int> ret;
        void spiralOrderInner(const vector<vector<int>> matrix, int s, int m, int n) {
            if (m < 1 || n < 1)
                return;
            if (m <= 1 || n <= 1) {
                for (int i = 0; i < m; ++i)
                    for (int j = 0; j < n; ++j)
                        ret.push_back(matrix[s + i][s + j]);
                return ;
            }

            for (int i = s, endIndex = s + n - 2; i <= endIndex; ++i ) ret.push_back(matrix[s][i]);
            for (int i = s, endIndex = s + m - 2; i <= endIndex; ++i ) ret.push_back(matrix[i][s + n - 1]);
            for (int i = s + n - 1; i > s; --i ) ret.push_back(matrix[s + m - 1][i]);
            for (int i = s + m - 1; i > s; --i ) ret.push_back(matrix[i][s]);

            spiralOrderInner(matrix, s + 1, m - 2, n - 2);
        }

        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            ret.clear();
            int m = matrix.size();
            if (m < 1) return ret;
            int n = matrix[0].size();
            spiralOrderInner(matrix, 0, m, n);
            return ret;
        }
};

For the Spiral Matrix II, both of the following recursive and iterative implementation are accepted:

class Solution {
    public:
        void genInner(vector<vector<int>> &matrix, int k, int s, int len) {
            if (1 == len) {
                matrix[s][s] = k;
                return ;
            }
            if (len <= 0) {
                return ;
            }

            for (int i = 0; i < len; ++i) matrix[s][s + i] = k++;
            for (int i = 1, col = s + len - 1; i < len; ++i) matrix[s + i][col] = k++;
            for (int i = s + len - 2, row = s + len - 1; i >= s; --i) matrix[row][i] = k++;
            for (int i = s + len - 2; i > s; --i) matrix[i][s] = k++;
            genInner(matrix, k, s + 1, len - 2);
        }

        vector<vector<int> > generateMatrix(int n) {
            vector<vector<int>> ret;
            if (n < 1) return ret;

            ret.resize(n);
            for (int i = 0; i < n; ++i) ret[i].resize(n);

            genInner(ret, 1, 0, n);
            return ret;
        }
};

And the following is the iterative one:

vector<vector<int> > generateMatrix(int n) {
    vector<vector<int>> ret;
    if (n < 1) return ret;

    ret.resize(n);
    for (int i = 0; i < n; ++i) ret[i].resize(n);

    int i = 0, j = 0, k = 1, layer = 0;
    int ns = n * n;
    int direct = 0;
    while (k <= ns) {
        i = layer, j = layer;
        while (j < n - layer) ret[i][j++] = k++;

        i = layer + 1, j = n - layer - 1;
        while (i < n - layer) ret[i++][j] = k++;

        i = n - layer - 1, j = n - layer - 2;
        while (j >= layer) ret[i][j--] = k++;

        i = n - layer - 2, j = layer;
        while (i > layer) ret[i--][j] = k++;

        ++layer;
    }
    return ret;
}

Further Reference: “Printing Matrix (2D array) in Spiral Order“.

Summary

LeetCode Spiral Matrix I and II is to test array index manipulation which can be done in both recursive and iterative manner to find the pattern of calculation

Written on May 9, 2013