Spiral Matrix 2 - Generate

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:

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

Example 2:

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

Similar Problems

• [Spiral Matrix 1 - Return](spiral-matrix-1-return)
• [Spiral Matrix 3 - Traverse from Given Starting Point](spiral-matrix-3-traverse-from-given-starting-point)
• [Spiral Matrix 4 - From Linked List](spiral-matrix-4-from-linked-list)

Solution

Video explanation

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

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/swBxPNPaLso" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Iterative just checking boundaries

We can reuse the solution from [Spiral Matrix 1 - Return#Method 1 - Iterative just checking boundaries](spiral-matrix-1-return.md/#method-1---iterative-just-checking-boundaries).

Code

Java

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;
	}
}

Python

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.