54. Spiral Matrix

MediumArrayMatrixSimulation
Leetcode Link

Problem Description

In this problem, we are tasked with traversing a 2D array (or matrix) in a spiral pattern. Imagine starting at the top-left corner of the matrix and going right, then down, then left, and then up, turning inward in a spiral shape, until we traverse every element in the matrix exactly once. The function should return a list of the elements of the matrix in the order they were visited during this spiral traversal.

Intuition

To solve this problem, we need to simulate the process of traveling around the matrix spiral. Essentially, we keep moving in the same direction (right initially) until we meet a boundary of the matrix or a previously visited cell. When we encounter such a boundary, we make a clockwise turn and continue the process.

There are two insightful approaches to this problem:

  1. Simulation Approach: We initiate four direction vectors (or in our case, a direction array dirs) that represent right, down, left, and up. We iterate over all elements in the matrix by taking steps in the initial direction until we can no longer move forward. At this point, we turn 90 degrees and continue. To avoid revisiting cells, we mark each visited cell by adding it to a set vis so that we know when to turn. The time complexity here is O(m x n) because we visit each element once, and the space complexity is also O(m x n) due to the extra space used to store visited cells.

  2. Layer-by-layer Simulation: Instead of marking visited cells, we can visualize the matrix as a series of concentric rectangular layers. We traverse these layers from the outermost to the innermost, peeling them away as we go. This approach requires careful handling of the indices to ensure we stay within the bounds of the current layer. This way of traversal helps to potentially reduce extra space usage because we don't explicitly need to keep track of visited cells.

In the provided solution code, we follow the simulation approach. We appropriately update our direction of movement based on the bounds of the matrix and whether we've visited a cell. The direction change is done by iterating over the dirs array and updating our row and column pointers i and j respectively. The result list ans stores the elements as we traverse the matrix.

Solution Approach

The given Python solution follows the Simulation Approach described in the intuition section.

  1. Initialization:

    • We define m and n which are the dimensions of the matrix (number of rows and number of columns respectively).
    • The dirs array dirs = (0, 1, 0, -1, 0) encodes the direction vectors. dirs[k] and dirs[k+1] together represent the direction we move in, with k starting at 0 and cycling through values 0 to 3 to represent right, down, left, and up in that order.
    • The i and j variables represent the current row and column positions in the matrix.
    • ans list is where we collect the elements of the matrix as we visit them.
  2. Visiting Elements:

    • We loop exactly m * n times, once for each element of the matrix.
    • Each time through the loop, we append the current element to the ans list and mark its position (i, j) as visited by adding it to the vis set.
  3. Moving Through the Matrix:

    • We calculate the next position (x, y) based on the current direction we are moving. This is done using the current values of i, j, and k.
    • Before we move to the next position, we check if the position is valid - it must be within bounds and not already visited. This is the if not 0 <= x < m or not 0 <= y < n or (x, y) in vis: check.
    • If the move is invalid, we change the direction by increasing k modulo 4. This works because if k is 3 and we add 1, (k + 1) % 4 will reset k back to 0.
    • Once the direction is confirmed as valid, we update i and j to move to the next position in the matrix.
  4. Handling Edge Cases:

    • Because we update the direction whenever we hit the edge of the matrix or a visited cell, the algorithm naturally handles non-square matrices and any edge cases where the spiral must turn inward.
  5. Completing the Spiral:

    • The process continues, circling around the matrix and moving inward until all elements have been added to ans.
  6. Space Optimization:

    • In the reference solution, it's suggested that instead of using a vis set to keep track of visited cells (contributing to space complexity of O(m x n)), we could modify the matrix itself to mark cells as visited. This could be done by adding a constant value which is outside the range of the matrix values, effectively using the input matrix as the vis state. This reduces the space complexity to O(1), provided the matrix can be modified and that the added constant is chosen such that it doesn't cause integer overflow.

The executed code follows this approach rigorously, and through simulation, delivers the correct spiral traversal of the input matrix. The attention to directional changes and boundary conditions ensures that all cases are handled smoothly.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using a small example where our input is a 2D matrix:

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

Now we'll walk through the solution step by step:

  1. Initialization:

    • m = 3 (3 rows), n = 3 (3 columns)
    • Direction array dirs = (0, 1, 0, -1, 0) indicates the x and y offsets for right, down, left, and up movements respectively.
    • We start at the top-left corner, so initial indices i = 0 and j = 0.
    • ans = [] will collect the elements in spiral order.
    • vis = set() to store visited positions.
  2. Visiting Elements:

    • We begin by appending matrix[0][0] to ans, so ans = [1].
    • We add (0, 0) to vis to mark it as visited.
  3. Moving Through the Matrix:

    • We calculate the next position using the current direction (right, k = 0), so x = i + dirs[k] = 0 and y = j + dirs[k+1] = 1.
    • This position is within bounds and not visited, so we move there and append matrix[0][1] to ans, making it [1, 2].
    • We repeat this process and append [3, 6, 9] to ans.
  4. Direction Change and Boundary Check:

    • After reaching the last column, we check the next right move and find it's out of bounds.
    • We then change direction to down (k = 1), and append [8, 7] to ans.
  5. Avoiding Visited Cells:

    • Next, we attempt to move left but the cell (2, 0) is visited.
    • We turn again, moving up and find the top center cell (0, 1) is also visited.
    • We turn right and add [4, 5] to the spiral traversal.
  6. Completing the Spiral:

    • We've now visited all cells, and ans is [1, 2, 3, 6, 9, 8, 7, 4, 5].
  7. Space Optimization (Optional):

    • A potentially more space-efficient approach might entail modifying the given matrix to mark visited elements if allowed.

By following the simulation approach, the function would return the traversal in spiral order as [1, 2, 3, 6, 9, 8, 7, 4, 5].

Python Solution

1class Solution:
2    def spiralOrder(self, matrix):
3        """
4        This function takes a matrix and returns a list of elements in spiral order.
5        """
6      
7        # Define matrix dimensions.
8        rows, cols = len(matrix), len(matrix[0])
9      
10        # Define directions for spiral movement (right, down, left, up).
11        directions = ((0, 1), (1, 0), (0, -1), (-1, 0))
12      
13        # Initialize row and column indices and the direction index.
14        row = col = direction_index = 0
15      
16        # Initialize the answer list and a set to keep track of visited cells.
17        result = []
18        visited = set()
19      
20        # Iterate over the cells of the matrix.
21        for _ in range(rows * cols):
22            # Append the current element to the result list.
23            result.append(matrix[row][col])
24            # Mark the current cell as visited.
25            visited.add((row, col))
26          
27            # Calculate the next cell's position based on the current direction.
28            next_row, next_col = row + directions[direction_index][0], col + directions[direction_index][1]
29          
30            # Check if the next cell is within bounds and not visited.
31            if not (0 <= next_row < rows) or not (0 <= next_col < cols) or (next_row, next_col) in visited:
32                # Change direction if out of bounds or cell is already visited.
33                direction_index = (direction_index + 1) % 4
34          
35            # Update the row and column indices to the next cell's position.
36            row += directions[direction_index][0]
37            col += directions[direction_index][1]
38      
39        # Return the result list.
40        return result
41

Java Solution

1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5    public List<Integer> spiralOrder(int[][] matrix) {
6        // Dimensions of the 2D matrix
7        int rowCount = matrix.length;
8        int colCount = matrix[0].length;
9        // Direction vectors for right, down, left, and up
10        int[] directionRow = {0, 1, 0, -1};
11        int[] directionCol = {1, 0, -1, 0};
12        // Starting point
13        int row = 0, col = 0;
14        // Index for the direction vectors
15        int directionIndex = 0;
16        // List to hold the spiral order
17        List<Integer> result = new ArrayList<>();
18        // 2D array to keep track of visited cells
19        boolean[][] visited = new boolean[rowCount][colCount];
20
21        for (int h = rowCount * colCount; h > 0; --h) {
22            // Add the current element to the result
23            result.add(matrix[row][col]);
24            // Mark the current cell as visited
25            visited[row][col] = true;
26            // Compute the next cell position
27            int nextRow = row + directionRow[directionIndex];
28            int nextCol = col + directionCol[directionIndex];
29            // Check if the next cell is out of bounds or visited
30            if (nextRow < 0 || nextRow >= rowCount || nextCol < 0 || nextCol >= colCount || visited[nextRow][nextCol]) {
31                // Update the direction index to turn right in the spiral order
32                directionIndex = (directionIndex + 1) % 4;
33                // Recompute the next cell using the new direction
34                nextRow = row + directionRow[directionIndex];
35                nextCol = col + directionCol[directionIndex];
36            }
37            // Move to the next cell
38            row = nextRow;
39            col = nextCol;
40        }
41        return result;
42    }
43}
44

C++ Solution

1class Solution {
2public:
3    vector<int> spiralOrder(vector<vector<int>>& matrix) {
4        if (matrix.empty()) return {}; // Return an empty vector if the matrix is empty
5      
6        int rows = matrix.size(), cols = matrix[0].size(); // rows and cols store the dimensions of the matrix
7        vector<int> directions = {0, 1, 0, -1, 0}; // Row and column increments for right, down, left, up movements
8        vector<int> result; // This vector will store the elements of matrix in spiral order
9        vector<vector<bool>> visited(rows, vector<bool>(cols, false)); // Keep track of visited cells
10      
11        int row = 0, col = 0, dirIndex = 0; // Start from the top-left corner and use dirIndex to index into directions
12      
13        for (int remain = rows * cols; remain > 0; --remain) {
14            result.push_back(matrix[row][col]); // Add the current element to result
15            visited[row][col] = true; // Mark the current cell as visited
16          
17            // Calculate the next cell position
18            int nextRow = row + directions[dirIndex], nextCol = col + directions[dirIndex + 1];
19          
20            // Change direction if next cell is out of bounds or already visited
21            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols || visited[nextRow][nextCol]) {
22                dirIndex = (dirIndex + 1) % 4; // Rotate to the next direction
23            }
24          
25            // Move to the next cell
26            row += directions[dirIndex];
27            col += directions[dirIndex + 1];
28        }
29        return result; // Return the result
30    }
31};
32

Typescript Solution

1function spiralOrder(matrix: number[][]): number[] {
2    const rowCount = matrix.length; // Number of rows in the matrix
3    const colCount = matrix[0].length; // Number of columns in the matrix
4    const result: number[] = []; // The array that will be populated and returned
5    const visited = new Array(rowCount).fill(0).map(() => new Array(colCount).fill(false)); // A 2D array to keep track of visited cells
6    const directions = [0, 1, 0, -1, 0]; // Direction array to facilitate spiral traversal: right, down, left, up
7    let remainingCells = rowCount * colCount; // Total number of cells to visit
8  
9    // Starting point coordinates and direction index
10    let row = 0;
11    let col = 0;
12    let dirIndex = 0;
13  
14    // Iterate over each cell, decrementing the count of remaining cells
15    for (; remainingCells > 0; --remainingCells) {
16        result.push(matrix[row][col]); // Add the current cell's value to the result
17        visited[row][col] = true; // Mark the current cell as visited
18
19        // Calculate the indices for the next cell in the current direction
20        const nextRow = row + directions[dirIndex];
21        const nextCol = col + directions[dirIndex + 1];
22
23        // Check if the next cell is out of bounds or already visited
24        if (nextRow < 0 || nextRow >= rowCount || nextCol < 0 || nextCol >= colCount || visited[nextRow][nextCol]) {
25            dirIndex = (dirIndex + 1) % 4; // Change direction (right -> down -> left -> up)
26        }
27
28        // Move to the next cell in the updated/current direction
29        row += directions[dirIndex];
30        col += directions[dirIndex + 1];
31    }
32  
33    return result; // Return the array containing the spiral order traversal of the matrix
34}
35

Time and Space Complexity

The time complexity of the function spiralOrder is O(m * n) where m is the number of rows and n is the number of columns in the input matrix. This is because the function iterates over every element in the matrix exactly once.

The space complexity of the function, however, is not O(1) as stated in the reference answer. Instead, it is O(m * n) because the function uses a set vis to track visited elements, which in the worst-case scenario, can grow to contain every element in the matrix.

😈
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 👨‍🏫