59. Spiral Matrix II

MediumArrayMatrixSimulation
Leetcode Link

Problem Description

The task is to create a square matrix (2-dimensional array) of a given size n where n is a positive integer. The matrix should be filled with numbers from 1 to n^2 (1 to n squared) following a spiral pattern. A spiral pattern means we start from the top-left corner (0,0) and fill the matrix to the right, then downwards, then to the left, and finally upwards, before moving inwards in a spiral manner and repeating the directions until the entire matrix is filled.

Intuition

The intuition behind the solution is to replicate the spiral movement by using direction vectors to move the filling process right, down, left, and up. We use a variable to track the value to be filled in the next cell, which begins at 1 and ends at n^2. To navigate the matrix:

  1. We maintain a direction vector dirs which contains tuples representing the direction of movement: right (0, 1), down (1, 0), left (0, -1), and up (-1, 0).
  2. We initialize our position at the start of the matrix (0,0)
  3. We iterate through the values from 1 to n^2, filling the cells of the matrix.
  4. After inserting a value, we check if the next step will go out of bounds or into a cell that already has a value. If so, we change direction by rotating to the next direction vector.
  5. This process is continued until all cells are filled accordingly maintaining the spiral order.

The solution uses modulo division to cycle through the directions, ensuring when we reach the end of the direction vector, it loops back to the beginning. This helps us maintain the spiral path without creating complex conditional statements.

Solution Approach

The solution applies a simulation approach, where we simulate the spiral movement within the matrix. Let's dissect the solution approach.

  1. We start by creating an n x n matrix filled with 0s to hold the values. This is achieved by the list comprehension [[0] * n for _ in range(n)].

  2. We define a dirs array which contains four tuples. Each tuple represents the direction change for each step in our spiral: right is (0, 1), down is (1, 0), left is (0, -1), and up is (-1, 0).

  3. We initialize three variables i, j, and k which represent the current row, current column, and current direction index, respectively.

  4. A for loop is used to iterate through the range from 1 to n^2, inclusive. During each iteration, we perform the following steps:

    • Place the current value v in the ans matrix at position (i, j).
    • Calculate the next position (x, y) by adding the current direction vector dirs[k] to the current position (i, j).
    • Check if the next position is out of bounds or if the cell has already been visited (non-zero value). If either is true, we change the direction by updating the value of k with (k + 1) % 4, which rotates to the next direction vector in dirs.
    • Update the current position (i, j) to the new position (x, y) based on the direction we are moving.
  5. The loop stops when all values from 1 to n^2 have been placed into the ans matrix.

By following this approach, we can generate the matrix with numbers from 1 to n^2 in spiral order dynamically for any size of n.

The use of a direction vector is a common technique in grid traversal problems. It simplifies the process of moving in the four cardinal directions without writing multiple if-else conditions. The modulo operator % assists in cycling through our direction vectors to maintain the correct spiral movement.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's assume n = 3 to illustrate the solution approach. Our goal is to fill a 3x3 matrix with numbers from 1 to 3^2 (which is 9), in a spiral pattern.

  1. We create an empty 3x3 matrix filled with 0's.

    1ans = [
    2  [0, 0, 0],
    3  [0, 0, 0],
    4  [0, 0, 0]
    5]
  2. The dirs array contains direction vectors: [(0, 1), (1, 0), (0, -1), (-1, 0)]. This represents right, down, left, and up movement respectively.

  3. We set i, j, and k to 0. Here, (i, j) is the current position (initially at the top-left corner), and k is the index for direction vectors (starting with right movement).

  4. We will fill the matrix with values from 1 to 9. For each value v, we do the following:

    • Place v at ans[i][j]. For the first iteration, we place 1 at ans[0][0].
    • Update the next position (x, y) by adding the direction vector to the current position (i, j).
    • If (x, y) is out of bounds or ans[x][y] is not 0, we update k to (k + 1) % 4 to change direction.
    • Move to (x, y) and repeat the process.
  5. We continue this process until all values are filled into the matrix. After the completion, the ans matrix looks like:

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

The steps are as follows: Start with the top-left corner (0,0), move right and fill 1, 2, 3, then move down to fill 4, move left for 5, move up for 6, again move right for 7, then go to the center and fill 8, and finally move right to fill 9.

This makes the ans matrix to have its elements in a spiral order, from 1 to 9. By doing so for any n, we can generate the desired spiral matrix.

Python Solution

1class Solution:
2    def generateMatrix(self, n: int) -> List[List[int]]:
3        # Initialize the matrix with zeros
4        matrix = [[0] * n for _ in range(n)]
5        # Define directions for movement: right, down, left, and up
6        directions = ((0, 1), (1, 0), (0, -1), (-1, 0))
7        # Initialize the starting point and direction index
8        row = column = direction_index = 0
9      
10        # Iterate over all values from 1 to n^2 to fill the matrix
11        for value in range(1, n * n + 1):
12            # Assign the current value to the matrix
13            matrix[row][column] = value
14            # Calculate the next position
15            next_row, next_column = row + directions[direction_index][0], column + directions[direction_index][1]
16            # Check if the next position is out of bounds or already filled
17            if next_row < 0 or next_column < 0 or next_row >= n or next_column >= n or matrix[next_row][next_column]:
18                # Change direction if the next position is invalid
19                direction_index = (direction_index + 1) % 4
20                # Recalculate the next position after changing the direction
21                next_row, next_column = row + directions[direction_index][0], column + directions[direction_index][1]
22            # Move to the next position
23            row, column = next_row, next_column
24      
25        # Return the filled matrix
26        return matrix
27

Java Solution

1public class Solution {
2
3    public int[][] generateMatrix(int n) {
4        // Initialize the matrix to be filled.
5        int[][] matrix = new int[n][n];
6      
7        // Starting point for the spiral is (0,0), top-left corner of the matrix.
8        int row = 0, col = 0;
9      
10        // 'dirIndex' is used to determine the current direction of the spiral.
11        int dirIndex = 0;
12
13        // Define directions for right, down, left, up movement.
14        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
15      
16        // Fill up the matrix with values from 1 to n squared.
17        for (int value = 1; value <= n * n; ++value) {
18            // Place the value into the matrix.
19            matrix[row][col] = value;
20          
21            // Calculate the next position using the current direction.
22            int nextRow = row + directions[dirIndex][0];
23            int nextCol = col + directions[dirIndex][1];
24          
25            // Check boundary conditions and whether the cell is already filled.
26            if (nextRow < 0 || nextCol < 0 || nextRow >= n || nextCol >= n || matrix[nextRow][nextCol] > 0) {
27                // Change direction: right -> down -> left -> up -> right ...
28                dirIndex = (dirIndex + 1) % 4;
29                // Calculate the position again after changing direction.
30                nextRow = row + directions[dirIndex][0];
31                nextCol = col + directions[dirIndex][1];
32            }
33          
34            // Move to the next cell.
35            row = nextRow;
36            col = nextCol;
37        }
38      
39        // Return the filled spiral matrix.
40        return matrix;
41    }
42  
43}
44

C++ Solution

1class Solution {
2public:
3    // Directions array to help navigate right, down, left, and up.
4    const int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
5
6    // Generates a n-by-n matrix filled with elements from 1 to n^2 in spiral order.
7    vector<vector<int>> generateMatrix(int n) {
8        vector<vector<int>> matrix(n, vector<int>(n));
9        int row = 0, col = 0, dirIndex = 0; // Initialize the starting point and direction index.
10
11        for (int value = 1; value <= n * n; ++value) {
12            // Fill in the current cell with the current value.
13            matrix[row][col] = value;
14
15            // Calculate the next cell's row and column indexes based on the current direction.
16            int nextRow = row + directions[dirIndex][0];
17            int nextCol = col + directions[dirIndex][1];
18
19            // If the next cell is out of bounds or already filled, change direction.
20            if (nextRow < 0 || nextCol < 0 || nextRow >= n || nextCol >= n || matrix[nextRow][nextCol] != 0) {
21                dirIndex = (dirIndex + 1) % 4; // Update direction index to turn clockwise.
22
23                // Recalculate the next cell's row and column indexes after changing direction.
24                nextRow = row + directions[dirIndex][0];
25                nextCol = col + directions[dirIndex][1];
26            }
27
28            // Move to the next cell.
29            row = nextRow;
30            col = nextCol;
31        }
32
33        return matrix; // Return the filled matrix.
34    }
35};
36

Typescript Solution

1function generateMatrix(n: number): number[][] {
2    // Initialising the matrix with 'undefined' values
3    let matrix = Array.from({ length: n }, () => new Array(n).fill(undefined));
4
5    // Directions represent right, down, left, up movements respectively.
6    let directions = [
7        [0, 1],  // Move right
8        [1, 0],  // Move down
9        [0, -1], // Move left
10        [-1, 0], // Move up
11    ];
12
13    // Starting position in the top-left corner of the matrix
14    let row = 0, col = 0;
15
16    // Filling out the matrix with values from 1 to n*n
17    for (let value = 1, directionIndex = 0; value <= n * n; value++) {
18        // Assign the current value to the current position
19        matrix[row][col] = value;
20      
21        // Calculate the next position using current direction
22        let nextRow = row + directions[directionIndex][0],
23            nextCol = col + directions[directionIndex][1];
24      
25        // Check if the next position is out of bounds or already filled
26        if (nextRow < 0 || nextRow === n || nextCol < 0 || nextCol === n || matrix[nextRow][nextCol] !== undefined) {
27            // Change direction if out of bounds or cell is already filled
28            directionIndex = (directionIndex + 1) % 4;
29
30            // Update next position after changing direction
31            nextRow = row + directions[directionIndex][0];
32            nextCol = col + directions[directionIndex][1];
33        }
34      
35        // Update current position to the next position
36        row = nextRow;
37        col = nextCol;
38    }
39
40    // Returning the filled matrix
41    return matrix;
42}
43

Time and Space Complexity

The given Python code generates a spiral matrix of size n x n, where n is the input to the method generateMatrix. Let's analyze both the time complexity and space complexity of the code.

Time Complexity:

The time complexity of this algorithm is determined by the number of elements that need to be filled into the matrix, which corresponds to every position in the matrix being visited once. Since the matrix has n x n positions, the algorithm has to perform n * n operations, one for each element.

Thus, the time complexity is O(n^2).

Space Complexity:

The space complexity includes the space taken up by the output matrix, and any additional space used by the algorithm for processing. In this case, the output matrix itself is of size n x n, so that takes O(n^2) space. The algorithm uses a small, constant amount of extra space for variables and the direction tuple dirs.

This means the additional space used by the algorithm does not grow with n, which makes it O(1). However, since the output matrix size is proportional to the square of n, we consider it in the overall space complexity.

Thus, the overall space complexity of the algorithm is O(n^2).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫