Skip to content

1914. Cyclically Rotating a Grid 👎

  • Time: $O(mnk)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
    const int m = grid.size();
    const int n = grid[0].size();
    int t = 0;      // the top
    int l = 0;      // the left
    int b = m - 1;  // the bottom
    int r = n - 1;  // the right

    while (t < b && l < r) {
      const int elementInThisLayer = 2 * (b - t + 1) + 2 * (r - l + 1) - 4;
      const int netRotations = k % elementInThisLayer;
      for (int rotate = 0; rotate < netRotations; ++rotate) {
        const int topLeft = grid[t][l];
        for (int j = l; j < r; ++j)
          grid[t][j] = grid[t][j + 1];
        for (int i = t; i < b; ++i)
          grid[i][r] = grid[i + 1][r];
        for (int j = r; j > l; --j)
          grid[b][j] = grid[b][j - 1];
        for (int i = b; i > t; --i)
          grid[i][l] = grid[i - 1][l];
        grid[t + 1][l] = topLeft;
      }
      ++t;
      ++l;
      --b;
      --r;
    }

    return grid;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int[][] rotateGrid(int[][] grid, int k) {
    final int m = grid.length;
    final int n = grid[0].length;
    int t = 0;     // the top
    int l = 0;     // the left
    int b = m - 1; // the bottom
    int r = n - 1; // the right

    while (t < b && l < r) {
      final int elementInThisLayer = 2 * (b - t + 1) + 2 * (r - l + 1) - 4;
      final int netRotations = k % elementInThisLayer;
      for (int rotate = 0; rotate < netRotations; ++rotate) {
        final int topLeft = grid[t][l];
        for (int j = l; j < r; ++j)
          grid[t][j] = grid[t][j + 1];
        for (int i = t; i < b; ++i)
          grid[i][r] = grid[i + 1][r];
        for (int j = r; j > l; --j)
          grid[b][j] = grid[b][j - 1];
        for (int i = b; i > t; --i)
          grid[i][l] = grid[i - 1][l];
        grid[t + 1][l] = topLeft;
      }
      ++t;
      ++l;
      --b;
      --r;
    }

    return grid;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
    m = len(grid)
    n = len(grid[0])
    t = 0  # the top
    l = 0  # the left
    b = m - 1  # the bottom
    r = n - 1  # the right

    while t < b and l < r:
      elementInThisLayer = 2 * (b - t + 1) + 2 * (r - l + 1) - 4
      netRotations = k % elementInThisLayer
      for _ in range(netRotations):
        topLeft = grid[t][l]
        for j in range(l, r):
          grid[t][j] = grid[t][j + 1]
        for i in range(t, b):
          grid[i][r] = grid[i + 1][r]
        for j in range(r, l, - 1):
          grid[b][j] = grid[b][j - 1]
        for i in range(b, t, -1):
          grid[i][l] = grid[i - 1][l]
        grid[t + 1][l] = topLeft
      t += 1
      l += 1
      b -= 1
      r -= 1

    return grid