# Cyclically Rotating a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/cyclically-rotating-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/cyclically-rotating-a-grid
**Data structures:** Array, Matrix
**Companies:** [Applied Intuition](https://scaleengineer.com/companies/applied-intuition)
---
## Problem
You are given an `m x n` integer matrix `grid`​​​, where `m` and `n` are both **even** integers, and an integer `k`.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:

![](https://assets.glich.co/dsa/cyclically-rotating-a-grid/image0.png)

A cyclic rotation of the matrix is done by cyclically rotating **each layer** in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the **counter-clockwise** direction. An example rotation is shown below:

![](https://assets.glich.co/dsa/cyclically-rotating-a-grid/image1.jpg) 

Return _the matrix after applying_ `k` _cyclic rotations to it_.

**Example 1:**

![](https://assets.glich.co/dsa/cyclically-rotating-a-grid/image2.png) 

**Input:** grid = [[40,10],[30,20]], k = 1
**Output:** [[10,20],[40,30]]
**Explanation:** The figures above represent the grid at every state.

**Example 2:**

**![](https://assets.glich.co/dsa/cyclically-rotating-a-grid/image3.png)** **![](https://assets.glich.co/dsa/cyclically-rotating-a-grid/image4.png)** **![](https://assets.glich.co/dsa/cyclically-rotating-a-grid/image5.png)** 

**Input:** grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
**Output:** [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
**Explanation:** The figures above represent the grid at every state.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `2 <= m, n <= 50`
* Both `m` and `n` are **even** integers.
* `1 <= grid[i][j] <= 5000`
* `1 <= k <= 109`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It performs the cyclic rotation `k` times, one rotation at a time for each layer. While simple to conceptualize, its performance is directly tied to the value of `k`, making it unsuitable for large rotation counts.
**Time:** O(k * m * n). For each of the `k` rotations, we iterate through almost all `m * n` cells of the grid. This is very slow when `k` is large. · **Space:** O(1). The rotation is performed in-place, using only a few extra variables for layer boundaries and temporary storage during swaps.
**Pros:** Simple to understand and implement as it directly follows the problem's description of a single rotation.; Space efficient, as it performs the rotation in-place with `O(1)` extra space.
**Cons:** Extremely inefficient for large values of `k` as it performs `k` full passes over the grid.; Will result in a 'Time Limit Exceeded' error for the given constraints on `k`.
### Explanation
The main idea is to have a loop that runs `k` times. Inside this loop, we iterate through each layer of the grid. The number of layers is determined by `min(m, n) / 2`. For each layer, we perform a single counter-clockwise rotation. This can be done in-place by saving one element (e.g., the top-left corner) in a temporary variable and then shifting all other elements one by one along the layer's boundary. This entire process of rotating every layer once is repeated `k` times.

```java
class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        // This outer loop makes the approach inefficient.
        for (int rot = 0; rot < k; rot++) {
            for (int i = 0; i < Math.min(m, n) / 2; i++) {
                int top = i, left = i;
                int bottom = m - 1 - i, right = n - 1 - i;
                
                // Store top-left element
                int temp = grid[top][left];
                
                // Shift top row (left to right)
                for (int j = left; j < right; j++) {
                    grid[top][j] = grid[top][j + 1];
                }
                // Shift right column (bottom to top)
                for (int j = top; j < bottom; j++) {
                    grid[j][right] = grid[j + 1][right];
                }
                // Shift bottom row (right to left)
                for (int j = right; j > left; j--) {
                    grid[bottom][j] = grid[bottom][j - 1];
                }
                // Shift left column (top to bottom)
                for (int j = bottom; j > top + 1; j--) {
                    grid[j][left] = grid[j - 1][left];
                }
                // Place stored element
                grid[top + 1][left] = temp;
            }
        }
        return grid;
    }
}
```
### Algorithm
1. Loop `count` from 1 to `k`.
2. Inside the loop, iterate through each layer `i` from `0` to `min(m, n) / 2 - 1`.
3. For each layer, perform one counter-clockwise rotation. This is done by:
    - Saving the top-left element `grid[i][i]` in a temporary variable.
    - Shifting elements on the top edge to the left.
    - Shifting elements on the right edge upwards.
    - Shifting elements on the bottom edge to the right.
    - Shifting elements on the left edge downwards.
    - Placing the saved temporary element into its new position `grid[i+1][i]`.
4. After the loops complete, return the modified `grid`.

## Optimized Layer-by-Layer Rotation
This approach avoids the costly simulation by calculating the final state of each layer directly. It leverages the property of modular arithmetic: rotating a layer with `L` elements `k` times is equivalent to rotating it `k % L` times. This reduces the problem from `k` operations to a single, efficient operation per layer.
**Time:** O(m * n). Each cell in the grid is visited a constant number of times (once to unroll into a list, and once to place back into the grid). · **Space:** O(m * n). A temporary list is used to store the elements of each layer. The total size of these lists is proportional to the number of elements in the grid.
**Pros:** Highly efficient and correctly handles large `k` due to the modulo operation.; The logic is straightforward: flatten, rotate the flattened list, and rebuild the layer.
**Cons:** Uses extra space proportional to the grid size to store the unrolled layers.
### Explanation
The core idea is to process each layer independently. For each layer, we first "unroll" it into a 1D list. This means traversing the layer's boundary in a consistent counter-clockwise order and adding each element to the list. Once we have the 1D representation, we find its size, `L`. The crucial optimization is realizing that we only need to perform `rot = k % L` rotations. A large `k` is now reduced to a small number. We can then easily find the new position of each element. Finally, we "roll" the correctly ordered elements from the list back onto the grid by traversing the layer's boundary again and placing the elements from their new, rotated positions in the list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        for (int i = 0; i < Math.min(m, n) / 2; i++) {
            // 1. Unroll the layer into a 1D list
            List<Integer> layerElements = new ArrayList<>();
            // Top row (left to right)
            for (int j = i; j < n - 1 - i; j++) layerElements.add(grid[i][j]);
            // Right col (top to bottom)
            for (int j = i; j < m - 1 - i; j++) layerElements.add(grid[j][n - 1 - i]);
            // Bottom row (right to left)
            for (int j = n - 1 - i; j > i; j--) layerElements.add(grid[m - 1 - i][j]);
            // Left col (bottom to top)
            for (int j = m - 1 - i; j > i; j--) layerElements.add(grid[j][i]);
            
            // 2. Calculate effective rotations
            int layerSize = layerElements.size();
            int rotations = k % layerSize;
            
            // 3. Roll the rotated elements back into the grid
            int listIndex = 0;
            // Top row
            for (int j = i; j < n - 1 - i; j++) grid[i][j] = layerElements.get((listIndex++ + rotations) % layerSize);
            // Right col
            for (int j = i; j < m - 1 - i; j++) grid[j][n - 1 - i] = layerElements.get((listIndex++ + rotations) % layerSize);
            // Bottom row
            for (int j = n - 1 - i; j > i; j--) grid[m - 1 - i][j] = layerElements.get((listIndex++ + rotations) % layerSize);
            // Left col
            for (int j = m - 1 - i; j > i; j--) grid[j][i] = layerElements.get((listIndex++ + rotations) % layerSize);
        }
        
        return grid;
    }
}
```
### Algorithm
1. Iterate through each layer `i` from `0` to `min(m, n) / 2 - 1`.
2. For the current layer `i`:
    a. **Unroll**: Traverse the layer's boundary in a counter-clockwise order and store all its elements in a 1D list (`layerElements`).
    b. **Calculate Rotations**: Determine the number of elements in the layer, `L`. The effective number of rotations is `rot = k % L`.
    c. **Roll Back**: Traverse the layer's boundary again in the same counter-clockwise order. For each position `j` (0-indexed) on the boundary, place the element from the 1D list at index `(j + rot) % L` back into the grid.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] grid;
public
  int[][] rotateGrid(int[][] grid, int k) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    for (int p = 0; p < Math.min(m, n) / 2; ++p) {
      rotate(p, k);
    }
    return grid;
  }
private
  void rotate(int p, int k) {
    List<Integer> nums = new ArrayList<>();
    for (int j = p; j < n - p - 1; ++j) {
      nums.add(grid[p][j]);
    }
    for (int i = p; i < m - p - 1; ++i) {
      nums.add(grid[i][n - p - 1]);
    }
    for (int j = n - p - 1; j > p; --j) {
      nums.add(grid[m - p - 1][j]);
    }
    for (int i = m - p - 1; i > p; --i) {
      nums.add(grid[i][p]);
    }
    int l = nums.size();
    k %= l;
    if (k == 0) {
      return;
    }
    for (int j = p; j < n - p - 1; ++j) {
      grid[p][j] = nums.get(k++ % l);
    }
    for (int i = p; i < m - p - 1; ++i) {
      grid[i][n - p - 1] = nums.get(k++ % l);
    }
    for (int j = n - p - 1; j > p; --j) {
      grid[m - p - 1][j] = nums.get(k++ % l);
    }
    for (int i = m - p - 1; i > p; --i) {
      grid[i][p] = nums.get(k++ % l);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> rotateGrid(vector<vector<int>> &grid, int k) {
    int m = grid.size(), n = grid[0].size();
    auto rotate = [&](int p, int k) {
      vector<int> nums;
      for (int j = p; j < n - p - 1; ++j) {
        nums.push_back(grid[p][j]);
      }
      for (int i = p; i < m - p - 1; ++i) {
        nums.push_back(grid[i][n - p - 1]);
      }
      for (int j = n - p - 1; j > p; --j) {
        nums.push_back(grid[m - p - 1][j]);
      }
      for (int i = m - p - 1; i > p; --i) {
        nums.push_back(grid[i][p]);
      }
      int l = nums.size();
      k %= l;
      if (k == 0) {
        return;
      }
      for (int j = p; j < n - p - 1; ++j) {
        grid[p][j] = nums[k++ % l];
      }
      for (int i = p; i < m - p - 1; ++i) {
        grid[i][n - p - 1] = nums[k++ % l];
      }
      for (int j = n - p - 1; j > p; --j) {
        grid[m - p - 1][j] = nums[k++ % l];
      }
      for (int i = m - p - 1; i > p; --i) {
        grid[i][p] = nums[k++ % l];
      }
    };
    for (int p = 0; p < min(m, n) / 2; ++p) {
      rotate(p, k);
    }
    return grid;
  }
};

```

### Python

```python
class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]: def rotate(p: int, k: int): nums = [] for j in range(p, n - p - 1): nums . append(grid[p][j]) for i in range(p, m - p - 1): nums . append(grid[i][n - p - 1]) for j in range(n - p - 1, p, - 1): nums . append(grid[m - p - 1][j]) for i in range(m - p - 1, p, - 1): nums . append(grid[i][p]) k %= len(nums) if k == 0: return nums = nums[k:] + nums[: k] k = 0 for j in range(p, n - p - 1): grid[p][j] = nums[k] k += 1 for i in range(p, m - p - 1): grid[i][n - p - 1] = nums[k] k += 1 for j in range(n - p - 1, p, - 1): grid[m - p - 1][j] = nums[k] k += 1 for i in range(m - p - 1, p, - 1): grid[i][p] = nums[k] k += 1 m, n = len(grid), len(grid[0]) for p in range(min(m, n) >> 1): rotate(p, k) return grid

```