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.
This approach involves extracting each layer of the matrix, performing a rotation on the linearized version, and then re-integrating the rotated data back into the matrix.
This Python implementation follows the outlined approach. We loop through each layer, extract elements into a list, perform the rotation using slicing based on the effective k, and then re-map elements back to their respective positions.
Time Complexity: O(m * n) as each element is visited once. Space Complexity: O(max(m, n)) due to the storage of one layer's elements.
In this approach, we directly manipulate the matrix's coordinates without requiring additional storage for layers. This is achieved by calculating the next position directly based on the current position and number of rotations.
This Java implementation calculates the final position for each coordinate in a layer by tracing the layers and directly determining the new position using modular arithmetic. This avoids needing a separate layer list outside of the loop.
Java
JavaScript
Time Complexity: O(m * n) since it visits each coordinate. Space Complexity: O(min(m, n)), for handling layer calculations in auxiliary arrays.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Layered Rotation Method | Time Complexity: O(m * n) as each element is visited once. Space Complexity: O(max(m, n)) due to the storage of one layer's elements. |
| Direct Coordinate Manipulation | Time Complexity: O(m * n) since it visits each coordinate. Space Complexity: O(min(m, n)), for handling layer calculations in auxiliary arrays. |
| Default Approach | — |
| 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. |
Leetcode-Cyclically Rotating a Grid • Coding For Dummies • 1,276 views views
Watch 4 more video solutions →Practice Cyclically Rotating a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor