Watch 5 video solutions for Cyclically Rotating a Grid, a medium level problem involving Array, Matrix, Simulation. This walkthrough by Coding For Dummies has 1,276 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthn == grid[i].length2 <= m, n <= 50m and n are even integers.1 <= grid[i][j] <= 50001 <= k <= 109Problem Overview: You are given an m x n grid and an integer k. Each rectangular layer of the matrix must be rotated cyclically k times in the counter‑clockwise direction. The outer ring rotates independently from inner rings, so the main task is correctly identifying layer boundaries and moving elements along their perimeter.
Approach 1: Layered Rotation Method (O(m*n) time, O(min(m,n)) space)
Process the grid one layer at a time. For a layer defined by top, bottom, left, right boundaries, extract all elements along its perimeter into a temporary list. The number of effective rotations is k % perimeter_length, which avoids unnecessary full cycles. Rotate the list and write values back along the same perimeter order. Every cell is visited a constant number of times, so the total runtime is O(m*n) with O(perimeter) temporary storage per layer. This approach is straightforward and easy to debug because the rotation happens on a linear representation of the ring.
This technique works well for problems involving matrix layer traversal. The key insight is recognizing that each ring forms a circular array. Once converted to a list, cyclic rotation becomes a simple index shift.
Approach 2: Direct Coordinate Manipulation (O(m*n) time, O(1) space)
Instead of extracting elements, compute the final position of each element directly. For every cell, determine which layer it belongs to using its minimum distance from the grid edges. From that layer you can compute the perimeter length and the element's offset along the ring. After applying (offset + k) % perimeter, convert the new offset back into grid coordinates and place the value in the rotated position.
This method avoids building temporary arrays and performs rotation purely through coordinate math. It achieves O(1) extra space while still scanning the grid once for O(m*n) time. The tradeoff is more complex index calculations along the ring edges. Problems focused on array manipulation and simulation often benefit from this style of direct coordinate mapping.
Recommended for interviews: The layered rotation method is usually expected. It clearly demonstrates understanding of matrix layers and cyclic rotation using k % perimeter. The direct coordinate approach is more space‑efficient but involves heavier index math, so it is typically considered an optimization after explaining the layer‑based solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Layered Rotation Method | O(m*n) | O(min(m,n)) | Best for readability and interviews; easy to implement by extracting each matrix ring. |
| Direct Coordinate Manipulation | O(m*n) | O(1) | When minimizing extra memory or practicing index math for matrix simulation problems. |