Problem description:

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

1
2
3
4
5
6
7
8
9
Example:

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

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        
        vector<vector<int> > res( n, vector<int>(n) );
        int k = 1, i = 0;
        	while( k <= n * n )
        	{
        		int j = i;
                    // four steps
        		while( j < n - i )             // 1. horizonal, left to right
        			res[i][j++] = k++;
        		j = i + 1;
        		while( j < n - i )             // 2. vertical, top to bottom
        			res[j++][n-i-1] = k++;
        		j = n - i - 2;
        		while( j > i )                  // 3. horizonal, right to left 
        			res[n-i-1][j--] = k++;
        		j = n - i - 1;
        		while( j > i )                  // 4. vertical, bottom to  top 
        			res[j--][i] = k++;
        		i++;      // next loop
        	}
        	return res;
        
    }
};

Solution 2:

Define the four edge point to do the traverse.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int top= 0, left= 0, bot= n-1, right= n-1;
        int count= 1;
        vector<vector<int>> res(n, vector<int>(n, 0));
        while(top<= bot && left<= right){
            for(int i= left; i<= right; i++){
                res[top][i]= count++;
            }
            top++;
            
            for(int i= top; i<= bot; i++){
                res[i][right]= count++;
            }
            right--;
            
            for(int i= right; i>= left; i--){
                res[bot][i]= count++;
            }
            bot--;
            
            for(int i= bot; i>= top; i--){
                res[i][left]= count++;
            }
            left++;
            
        }
        return res;
    }
};