1914. Cyclically Rotating a Grid

MediumArrayMatrixSimulation
Leetcode Link

Problem Description

The problem presents a grid, which is a 2-dimensional matrix of integers of m rows and n columns, where both m and n are even numbers. This grid has several concentric rectangular layers, like an onion. The task is to perform cyclic rotations on each of these layers. A single rotation moves each element to the position of the next element in the counter-clockwise direction within the layer it belongs to.

Imagine holding the outermost ring (layer) of the grid and rotating it left so that each item shifts one place along the ring. A full rotation would bring every element back to its original position. To achieve a cyclic rotation, you'd keep rotating until the specified number of rotations k is reached. However, to reduce unnecessary rotations, the real number of rotations needed is k modulo the total number of elements in the ring, as repeating the total number of elements in the ring's rotations would result in the original ring configuration.

The problem asks us to perform this operation k times on each layer and return the new grid configuration.

Intuition

To solve this problem, an intuitive approach is to treat each layer of the grid as a linear list of numbers. By flattening each layer into a list, we can perform rotations on this list directly, which simplifies the process of shifting elements. To flatten a layer, we traverse the perimeter of the rectangular layer, adding each element to the list. Once the list is assembled, we perform the rotations.

Since a full rotation of the list would result in the original configuration of the layer, we only need to rotate k times modulo the size of the list. This is done to eliminate the extra full rotations, leaving us with the remainder of k rotations that actually change the element positions.

The rotation itself is simple—we split the list into two parts: the first k elements and the remaining elements. We then concatenate these two parts by placing the second part at the front and the first part at the end.

The final step is to put the rotated list back into the correct positions on the grid. We must take care to place each element back into its original layer, going counter-clockwise around the rectangle. This process is reversed from the flattening step and requiring careful index calculation to ensure each element goes back to the correct position in the grid.

Overall, the main algorithm can be divided into 3 steps for each layer:

  1. Flatten the layer into a list.
  2. Rotate the list.
  3. Put the rotated elements back into their positions on the grid.

We apply this process starting from the outermost layer and moving inward until all layers have been rotated.

Solution Approach

The reference solution defines an inner function rotate that performs the rotation for a specific layer p of the grid, with p starting from 0 for the outermost layer and increasing to reach the inner layers. The layers are processed from outermost to innermost by a loop that calls the rotate function for each layer.

Here is the step-by-step breakdown of the solution:

  1. Initialization and Outer Loop:

    • First, the dimensions of the grid m and n are stored.
    • An outer loop iterates over each layer of the grid, starting with p = 0 for the outermost layer and incrementing p until it reaches the innermost layer. The stopping condition of the loop is until p reaches min(m, n) >> 1, i.e., half of the minimum of m and n, because there are that many layers in an m x n grid where both m and n are even.
  2. Layer Flattening:

    • Inside the rotate function, an empty list nums is created to represent the flattened layer.
    • Four for loops are used to traverse the rectangle's perimeter and fill nums with the elements in the layer, going counter-clockwise starting from the top-left corner of the layer.
  3. Calculating Effective Rotations:

    • The number of effective rotations k is calculated using the modulo operator (%) with respect to the length of nums. This is because rotating a list by its own length returns it to its original order, so any multiples of the list length can be ignored in the count of rotations.
  4. Rotating the Flattened Layer:

    • Rotations are performed by reassigning the values in nums such that it becomes nums[k:] + nums[:k]. This effectively moves the first k elements to the end of the list while moving the rest to the front.
  5. Putting Elements Back:

    • The rotated list is then put back into the grid. This involves reversing the process of flattening the layer: it uses four for loops that assign the rotated values from nums back into their respective positions in the grid. The variable k used here is distinct from the number of rotations and is instead an index into the nums list. With each assignment, k is incremented to move to the next element in nums.
  6. Return the Result:

    • After all layers have been rotated, the modified grid is returned as the final result.

This solution makes use of space to simplify the problem—flattening each layer into a list allows for straightforward rotation. The loops for putting the elements back ensure that the new values are assigned into proper positions according to the original layers' topology. This layer-by-layer approach is an effective way to modularize the problem and handle complex, multi-dimensional manipulations in a controllable manner.

Example Walkthrough

Let's take a grid of size 4x4 as an example to walk you through the solution process for cyclic rotation. Assume our grid looks as follows and we want to perform k = 2 rotations:

11 2 3 4
25 6 7 8
39 10 11 12
413 14 15 16

With m = 4 and n = 4, we have two layers to rotate. We will go through the steps of the solution approach for the outermost layer (p = 0), as the same steps would apply to the inner layers:

  1. Initialization and Outer Loop:

    • We start with p = 0, and since min(m, n) >> 1 equals 2, our loop will process two layers.
  2. Layer Flattening:

    • We flatten the outermost layer (when p = 0) by adding the elements in counter-clockwise order to a list nums:
      1nums = [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5]
    1
  3. Calculating Effective Rotations:

    • There are 12 elements in nums, and we want to rotate k = 2 times. 2 % 12 is 2, so we will rotate the list by 2 elements.
  4. Rotating the Flattened Layer:

    • We rotate nums by 2 places to get the new rotated list:
      1nums = [3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 1, 2]
  5. Putting Elements Back:

    • We put the elements back into the grid starting from where we began unrolling the layer, in the counter-clockwise direction:
      11 becomes 3, 2 becomes 4, 3 becomes 8, and so on, resulting in the grid:
      2
      33 4 8 12
      42 6 7 16
      51 10 11 15
      65 9  14 13
  6. Repeat for Next Layers:

    • Now, we'd repeat the process for the next layer (when p = 1, the inner 2x2 grid). Since k = 2, the inner grid would simply swap positions of elements.
    • The final grid after applying the process for the inner layer would be:
      13 4  8 12
      22 7 11 16
      31 6 10 15
      45 9 14 13

After performing the above steps for all layers, we have completed the rotations for each concentric rectangle in the grid, and the problem is solved. The grid we return represents the state of the original grid after 2 cyclic rotations have been applied to each layer.

Python Solution

1class Solution:
2    def rotate_grid(self, grid: List[List[int]], k: int) -> List[List[int]]:
3        # Helper function to rotate the layer of the grid at depth p by k positions
4        def rotate_layer(depth: int, rotations: int):
5            elements = []
6          
7            # Extract the elements of the current layer
8            # Top row, left to right
9            for col in range(depth, cols - depth - 1):
10                elements.append(grid[depth][col])
11            # Right column, top to bottom
12            for row in range(depth, rows - depth - 1):
13                elements.append(grid[row][cols - depth - 1])
14            # Bottom row, right to left
15            for col in range(cols - depth - 1, depth, -1):
16                elements.append(grid[rows - depth - 1][col])
17            # Left column, bottom to top
18            for row in range(rows - depth - 1, depth, -1):
19                elements.append(grid[row][depth])
20          
21            # Calculate the effective number of rotations needed
22            rotations %= len(elements)
23          
24            # Skip the rotation if no rotation is needed
25            if rotations == 0:
26                return
27          
28            # Perform the rotation
29            elements = elements[rotations:] + elements[:rotations]
30            index = 0
31          
32            # Reassign the rotated values back to the grid
33            # Top row, left to right
34            for col in range(depth, cols - depth - 1):
35                grid[depth][col] = elements[index]
36                index += 1
37            # Right column, top to bottom
38            for row in range(depth, rows - depth - 1):
39                grid[row][cols - depth - 1] = elements[index]
40                index += 1
41            # Bottom row, right to left
42            for col in range(cols - depth - 1, depth, -1):
43                grid[rows - depth - 1][col] = elements[index]
44                index += 1
45            # Left column, bottom to top
46            for row in range(rows - depth - 1, depth, -1):
47                grid[row][depth] = elements[index]
48                index += 1
49
50        rows, cols = len(grid), len(grid[0])
51        # Rotate each layer of the grid
52        for depth in range(min(rows, cols) // 2):  # >> 1 is replaced with // 2 for clarity
53            rotate_layer(depth, k)
54      
55        return grid
56

Java Solution

1class Solution {
2    private int rowCount; // The number of rows in the grid
3    private int colCount; // The number of columns in the grid
4    private int[][] grid; // The grid to be rotated
5
6    public int[][] rotateGrid(int[][] grid, int k) {
7        rowCount = grid.length; // Initialize the number of rows
8        colCount = grid[0].length; // Initialize the number of columns
9        this.grid = grid; // Set the instance grid variable to the input grid
10
11        // Iterate over the layers of the grid
12        for (int layer = 0; layer < Math.min(rowCount, colCount) / 2; ++layer) {
13            rotateLayer(layer, k); // Rotate each layer k times
14        }
15
16        return grid; // Return the rotated grid
17    }
18
19    private void rotateLayer(int layer, int rotations) {
20        List<Integer> elements = new ArrayList<>(); // Store the elements of the current layer
21
22        // Top row, left to right
23        for (int col = layer; col < colCount - layer - 1; ++col) {
24            elements.add(grid[layer][col]);
25        }
26      
27        // Right column, top to bottom
28        for (int row = layer; row < rowCount - layer - 1; ++row) {
29            elements.add(grid[row][colCount - layer - 1]);
30        }
31      
32        // Bottom row, right to left
33        for (int col = colCount - layer - 1; col > layer; --col) {
34            elements.add(grid[rowCount - layer - 1][col]);
35        }
36      
37        // Left column, bottom to top
38        for (int row = rowCount - layer - 1; row > layer; --row) {
39            elements.add(grid[row][layer]);
40        }
41
42        int totalElements = elements.size(); // Total number of elements in the current layer
43        rotations %= totalElements; // Normalize rotations to the range of 0 to totalElements - 1
44
45        // Return early if no rotation is needed
46        if (rotations == 0) {
47            return;
48        }
49
50        // Apply the rotation to the layer
51        for (int col = layer; col < colCount - layer - 1; ++col) {
52            grid[layer][col] = elements.get((rotations++) % totalElements);
53        }
54        for (int row = layer; row < rowCount - layer - 1; ++row) {
55            grid[row][colCount - layer - 1] = elements.get((rotations++) % totalElements);
56        }
57        for (int col = colCount - layer - 1; col > layer; --col) {
58            grid[rowCount - layer - 1][col] = elements.get((rotations++) % totalElements);
59        }
60        for (int row = rowCount - layer - 1; row > layer; --row) {
61            grid[row][layer] = elements.get((rotations++) % totalElements);
62        }
63    }
64}
65

C++ Solution

1class Solution {
2public:
3    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
4        // Obtain the number of rows and columns of the grid.
5        int numRows = grid.size(), numCols = grid[0].size();
6      
7        // Lambda function to rotate the p-th layer of the grid.
8        auto rotateLayer = [&](int layer, int rotations) {
9            vector<int> layerElements;
10          
11            // Store the top row of the current layer.
12            for (int col = layer; col < numCols - layer - 1; ++col) {
13                layerElements.push_back(grid[layer][col]);
14            }
15            // Store the right column of the current layer.
16            for (int row = layer; row < numRows - layer - 1; ++row) {
17                layerElements.push_back(grid[row][numCols - layer - 1]);
18            }
19            // Store the bottom row of the current layer.
20            for (int col = numCols - layer - 1; col > layer; --col) {
21                layerElements.push_back(grid[numRows - layer - 1][col]);
22            }
23            // Store the left column of the current layer.
24            for (int row = numRows - layer - 1; row > layer; --row) {
25                layerElements.push_back(grid[row][layer]);
26            }
27          
28            // Calculate effective number of rotations needed as it may be larger
29            // than the number of elements in the layer.
30            int layerSize = layerElements.size();
31            rotations %= layerSize;
32          
33            // If no rotations needed, just return.
34            if (rotations == 0) {
35                return;
36            }
37          
38            // Rotate the top row of the current layer.
39            for (int col = layer; col < numCols - layer - 1; ++col) {
40                grid[layer][col] = layerElements[(rotations++) % layerSize];
41            }
42            // Rotate the right column of the current layer.
43            for (int row = layer; row < numRows - layer - 1; ++row) {
44                grid[row][numCols - layer - 1] = layerElements[(rotations++) % layerSize];
45            }
46            // Rotate the bottom row of the current layer.
47            for (int col = numCols - layer - 1; col > layer; --col) {
48                grid[numRows - layer - 1][col] = layerElements[(rotations++) % layerSize];
49            }
50            // Rotate the left column of the current layer.
51            for (int row = numRows - layer - 1; row > layer; --row) {
52                grid[row][layer] = layerElements[(rotations++) % layerSize];
53            }
54        };
55      
56        // Loop through each layer from the outermost to the innermost.
57        for (int layer = 0; layer < min(numRows, numCols) / 2; ++layer) {
58            rotateLayer(layer, k);
59        }
60      
61        // Return the rotated grid.
62        return grid;
63    }
64};
65

Typescript Solution

1function rotateGrid(grid: number[][], rotations: number): number[][] {
2    const rowCount = grid.length;
3    const colCount = grid[0].length;
4
5    // Function to rotate a single layer of the grid by 'rotations' times
6    const rotateLayer = (layerIndex: number, rotationCount: number) => {
7        // Collect edge elements of the layer into 'layerElements'
8        const layerElements: number[] = [];
9        for (let col = layerIndex; col < colCount - layerIndex - 1; ++col) {
10            layerElements.push(grid[layerIndex][col]);
11        }
12        for (let row = layerIndex; row < rowCount - layerIndex - 1; ++row) {
13            layerElements.push(grid[row][colCount - layerIndex - 1]);
14        }
15        for (let col = colCount - layerIndex - 1; col > layerIndex; --col) {
16            layerElements.push(grid[rowCount - layerIndex - 1][col]);
17        }
18        for (let row = rowCount - layerIndex - 1; row > layerIndex; --row) {
19            layerElements.push(grid[row][layerIndex]);
20        }
21
22        // Normalize the rotation count to the size of layerElements
23        const layerSize = layerElements.length;
24        rotationCount %= layerSize;
25        if (rotationCount === 0) {
26            return; // No rotation needed
27        }
28
29        // Rotate the elements in the layer by 'rotationCount'
30        let index = rotationCount;
31        for (let col = layerIndex; col < colCount - layerIndex - 1; ++col) {
32            grid[layerIndex][col] = layerElements[index++ % layerSize];
33        }
34        for (let row = layerIndex; row < rowCount - layerIndex - 1; ++row) {
35            grid[row][colCount - layerIndex - 1] = layerElements[index++ % layerSize];
36        }
37        for (let col = colCount - layerIndex - 1; col > layerIndex; --col) {
38            grid[rowCount - layerIndex - 1][col] = layerElements[index++ % layerSize];
39        }
40        for (let row = rowCount - layerIndex - 1; row > layerIndex; --row) {
41            grid[row][layerIndex] = layerElements[index++ % layerSize];
42        }
43    };
44
45    // Rotate each concentric layer of the grid starting from the outermost layer
46    const numLayers = Math.min(rowCount, colCount) >> 1;
47    for (let layerIndex = 0; layerIndex < numLayers; ++layerIndex) {
48        rotateLayer(layerIndex, rotations);
49    }
50
51    // Return the grid after all rotations are applied
52    return grid;
53}
54

Time and Space Complexity

Time Complexity

The time complexity of the function primarily comes from the rotations performed layer by layer (from the outermost layer to the innermost). For each layer, we traverse all the elements in that layer to collect them into a list, and then write them back after the k rotations are applied.

Assuming the grid is m x n:

  • There are min(m, n) / 2 layers to rotate because the deepest layer is limited by the shorter dimension of the grid.
  • Each layer contains approximately 2*(m - 2p) + 2*(n - 2p) - 4 elements, where p is the current layer index (starting at 0). The -4 accounts for the corner elements being counted twice.
  • Summing this over all layers gives a series which is somewhat less than 2*m*n in total since the inner layers have fewer elements.
  • Therefore, the time complexity is essentially linear with respect to the total number of elements, leading to a total time complexity of O(m*n).

Space Complexity

The extra space complexity comes from two sources: the nums list that stores the border elements for each layer, and the recursion stack due to the rotate helper function. However, the helper function does not call itself recursively, so there's only ever one rotate function call active at a time.

The space required for the nums list is the longest when handling the outermost layer. Maximum space used would be for the next-to-largest possible layer, which is roughly 2*m + 2*n - 4. However, since the layers are processed one by one and the content of nums is overwritten for each layer rotation, this does not scale with the number of layers.

As a result, the space complexity of the algorithm is O(m + n) due to the nums list needed for rotating each layer.


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