Scale Engineer

Cyclically Rotating a Grid

Med
#1747Time: 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.1 company
Data structures
ArrayMatrix
Companies
Applied Intuition

Prompt

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 <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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);    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem