1914. Cyclically Rotating a Grid

1914. Cyclically Rotating a Grid

Difficulty: Medium

Topics: Senior, Array, Matrix, Simulation, Weekly Contest 247

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:

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:

Return the matrix after applying k cyclic rotations to it.

Example 1:

• 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:

• 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 <= 10⁹

Hint:

1. First, you need to consider each layer separately as an array.
2. Just cycle this array and then re-assign it.

Solution:

The solution extracts each layer of the matrix into a 1D array, performs a counter-clockwise rotation by k positions (modulo the layer’s length), and then places the rotated values back into the layer in the correct order. This process is repeated for all layers.

Approach:

• Since both m and n are even, the number of layers is min(m, n) / 2.
• For each layer, extract its elements in counter-clockwise order: top row → right column → bottom row → left column.
• Compute effective rotations: rot = k % len(elements).
• Rotate the array using array_slice to move the first rot elements to the end (counter-clockwise = shift left).
• Place the rotated elements back into the grid in the same traversal order.

Let's implement this solution in PHP: 1914. Cyclically Rotating a Grid

<?php
/**
 * @param Integer[][] $grid
 * @param Integer $k
 * @return Integer[][]
 */
function rotateGrid(array $grid, int $k): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo rotateGrid([[40,10],[30,20]], 1) . "\n";                                           // Output: [[10,20],[40,30]]
echo rotateGrid([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], 2) . "\n";            // Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
?>

Explanation:

• Layer extraction order matches the rotation direction (counter-clockwise), so rotating the 1D array corresponds to the required layer rotation.
• Modulo operation reduces large k (up to 10⁹) to at most the layer’s perimeter length, making the solution efficient.
• Traversal for reinsertion mirrors the extraction order to correctly place rotated elements into the grid.
• The algorithm works for any even dimensions, with a straightforward way to handle each rectangular concentric layer.

Complexity

• Time Complexity: O(m × n)
  • Each element is visited a constant number of times (once to extract, once to reinsert).
  • Layers are processed independently, and total elements = m × n.
• Space Complexity: O(m + n), In each layer, we store its perimeter elements in a temporary array. The largest perimeter is at the outermost layer: 2 × (m + n) - 4, which is O(m + n).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub