Problem

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Examples

Example 1:

1
2
3
4
5
6

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

Example 2:

1
2
3
4
5
6
7

Input: n = 4
Output: [
	[1, 2, 3, 4],
	[12, 13, 14, 5],
	[11, 16, 15, 6],
	[10, 9, 8, 7]
]

Similar Problems

Solution

Video explanation

Here is the video explaining below method in detail. Please check it out:

Method 1 - Iterative just checking boundaries

We can reuse the solution from Spiral Matrix 1 - Return#Method 1 - Iterative just checking boundaries.

Code

 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
32
33
34
35
36

public class Solution {
	public int[][] generateMatrix(int n) {
		int[][] ans = new int[n][n];
		
		int top = 0;
		int bottom = n - 1;
		int left = 0;
		int right = n - 1;

        int num = 1;
	
		while (num <= n * n) {
			for (int i = left; i<= right; i++) {
				ans[top][i] = num++;
			}
			top++;
	
			for (int i = top; i<= bottom; i++) {
				ans[i][right] = num++;
			}
			right--;

			for (int i = right; i >= left; i--) {
				ans[bottom][i] = num++;
			}
			bottom--;
			
			for (int i = bottom; i >= top; i--) {
				ans[i][left] = num++;
			}
			left++;
		}
	
		return ans;
	}
}
 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
32
33
34
35
36

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # Step 1: Initialise an n x n matrix with zeros
        matrix: List[List[int]] = [[0] * n for _ in range(n)]
        
        # Step 2: Define boundaries
        top, bottom, left, right = 0, n - 1, 0, n - 1
        num = 1  # Start filling with 1
        
        # Step 3: Traverse the boundaries
        while num <= n * n:
            # Traverse top row (left to right)
            for col in range(left, right + 1):
                matrix[top][col] = num
                num += 1
            top += 1  # Shrink top boundary
            
            # Traverse right column (top to bottom)
            for row in range(top, bottom + 1):
                matrix[row][right] = num
                num += 1
            right -= 1  # Shrink right boundary
            
            # Traverse bottom row (right to left)
            for col in range(right, left - 1, -1):
                matrix[bottom][col] = num
                num += 1
            bottom -= 1  # Shrink bottom boundary
            
            # Traverse left column (bottom to top)
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = num
                num += 1
            left += 1  # Shrink left boundary
        
        return matrix

Complexity

  • ⏰ Time complexity: O(n^2), since the matrix has n^2 elements, and each element is processed once.
  • 🧺 Space complexity: O(n^2) for the matrix space.