59. Spiral Matrix II

59. Spiral Matrix II

1 Description #

source: https://leetcode.com/problems/spiral-matrix-ii/ Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Example 1:

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

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

1 <= n <= 20

2 Solution #

class Solution {
public:

    vector<vector<int>> generateMatrix(int n) {
	// Space complexity: O(n * n)
	// Time complexity: O(n * n)
	// faster than 100.00% of C++ online submissions for Spiral Matrix II

	std::vector<std::vector<int>> result;
	result.reserve(n);
	for(int i = 0; i< n; i++){
	    std::vector<int> init(n, 0);
	    result.push_back(init);
	}

	int up = 0, down = n - 1, left = 0, right = n - 1;
	int j = 0;

	while(j < n * n){
	    for(int i = left; i <= right && j < n*n; i++){
		result[up][i] = ++j;
	    }

	    for(int i = up + 1; i <= down && j < n *n; i++){
		result[i][right] = ++j;
	    }

	    for(int i = right - 1; i >= left && j < n * n; i--){
		result[down][i] = ++j;
	    }

	    for(int i = down - 1; i > up && j < n * n; i--){
		result[i][left] = ++j;
	    }

	    left++, right--, up++, down--;
	}

	return result;
    }
};