# 54. Spiral Matrix

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

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

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

# Solution

Approach 1: Layer by layer or step by step.

# Code (Python)

Approach 1:

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # layer by layer
        if not matrix or not matrix[0]:
            return []
        height, width = len(matrix), len(matrix[0])
        layer = 0
        direction = 0
        result = []
        while len(result) < height * width:
            if direction == 0:
                result.extend(matrix[layer][layer:width-layer])
            elif direction == 1:
                result.extend((matrix[row][width-layer-1] for row in range(layer + 1, height - layer)))
            elif direction == 2:
                result.extend(matrix[height-layer-1][layer:width-layer-1][::-1])
            else:
                result.extend([matrix[row][layer] for row in range(layer + 1, height - layer - 1)][::-1])
                layer += 1
            direction = (direction + 1) % 4
        return result

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # step by step
        # this solution edits the matrix to mark them as visited
        if not matrix or not matrix[0]:
            return []
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        current = (0, 0)
        result = []
        current_direction = 0
        while True: # OR: while len(result) < len(matrix) * len(matrix)[0]
            result.append(matrix[current[0]][current[1]])
            matrix[current[0]][current[1]] = '-'
            next_position = self._generate_next(current, current_direction, directions, matrix)
            if next_position:
                current = next_position
            else:
                current_direction = (current_direction + 1) % 4
                next_position = self._generate_next(current, current_direction, directions, matrix)
                if next_position:
                    current = next_position
                else:
                    break
        return result
    
    def _generate_next(self, coord, direction, directions, matrix):
        next_coord = (coord[0] + directions[direction][0], coord[1] + directions[direction][1])
        if 0 <= next_coord[0] < len(matrix) and 0 <= next_coord[1] < len(matrix[0]) and matrix[next_coord[0]][next_coord[1]] != '-':
            return next_coord
        else:
            return None

# Code (C++)

Approach 1:

class Solution {
private:
    int nextStep[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> spiral;
        int m = matrix.size();
        if (m == 0) return spiral;
        int n = matrix[0].size();
        int rowHead = 0;
        int rowTail = m - 1;
        int colHead = 0;
        int colTail = n - 1;
        while (rowHead < rowTail && colHead < colTail)
        {
/*
            // Layer by layer.
            // e.g., 1 2 3
            //       4 5 6
            //       7 8 9
            // We do: 1->2, 3->6, 9->8, 7->4.
            for (int col = colHead; col < colTail; ++col)
            {
                spiral.push_back(matrix[rowHead][col]);
            }
            for (int row = rowHead; row < rowTail; ++row)
            {
                spiral.push_back(matrix[row][colTail]);
            }
            for (int col = colTail; col > colHead; --col)
            {
                spiral.push_back(matrix[rowTail][col]);
            }
            for (int row = rowTail; row > rowHead; --row)
            {
                spiral.push_back(matrix[row][colHead]);
            }
*/
            // Step by step.
            int row = rowHead;
            int col = colHead;
            int stepIdx = 0;
            do
            {
                spiral.push_back(matrix[row][col]);
                int nextRow = row + nextStep[stepIdx][0];
                int nextCol = col + nextStep[stepIdx][1];
                if (nextRow < rowHead || nextRow > rowTail || nextCol < colHead || nextCol > colTail)
                {
                    stepIdx = (stepIdx + 1) % 4;
                }
                row += nextStep[stepIdx][0];
                col += nextStep[stepIdx][1];
            }
            while (row != rowHead || col != colHead);

            rowHead++;
            rowTail--;
            colHead++;
            colTail--;
        }
        // e.g., 1 2 3    1    1 2 3
        //       4 5 6 or 2 or
        //       7 8 9    3
        if (rowHead == rowTail)
        {
            for (int col = colHead; col <= colTail; ++col)
            {
                spiral.push_back(matrix[rowHead][col]);
            }
        }
        else if (colHead == colTail) // need to be "else if".
        {
            for (int row = rowHead; row <= rowTail; ++row)
            {
                spiral.push_back(matrix[row][colHead]);
            }
        }
        return spiral;
    }
};