Skip to content

1914. Cyclically Rotating a Grid

Description

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

Solutions

Solution 1: Layer-by-Layer Simulation

Thinking

Layers are disjoint cycles and \(k\) may exceed a cycle length, so stepping cell by cell wastes work. Flatten each layer clockwise, reduce \(k\) modulo its length, then write back.

Collect top, right, bottom, and left in that order and restore in the same order. Layers are independent, so the total time is linear in the grid size.

First, we compute the number of layers in the matrix, denoted by \(p\), and then simulate the cyclic rotation layer by layer from the outside to the inside.

For each layer, we traverse clockwise and append the elements on the top, right, bottom, and left edges to an array \(nums\) in order. Let the length of \(nums\) be \(l\). Next, we take \(k \bmod l\). Then, starting from index \(k\) in the array, we write the elements back to the matrix along the top, right, bottom, and left edges in order.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m + n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix, respectively.

 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:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        def rotate(p: int, k: int):
            nums = []
            for j in range(p, n - p - 1):
                nums.append(grid[p][j])
            for i in range(p, m - p - 1):
                nums.append(grid[i][n - p - 1])
            for j in range(n - p - 1, p, -1):
                nums.append(grid[m - p - 1][j])
            for i in range(m - p - 1, p, -1):
                nums.append(grid[i][p])
            k %= len(nums)
            if k == 0:
                return
            nums = nums[k:] + nums[:k]
            k = 0
            for j in range(p, n - p - 1):
                grid[p][j] = nums[k]
                k += 1
            for i in range(p, m - p - 1):
                grid[i][n - p - 1] = nums[k]
                k += 1
            for j in range(n - p - 1, p, -1):
                grid[m - p - 1][j] = nums[k]
                k += 1
            for i in range(m - p - 1, p, -1):
                grid[i][p] = nums[k]
                k += 1

        m, n = len(grid), len(grid[0])
        for p in range(min(m, n) >> 1):
            rotate(p, k)
        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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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);
        }
    }
}

 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
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        auto rotate = [&](int p, int k) {
            vector<int> nums;
            for (int j = p; j < n - p - 1; ++j) {
                nums.push_back(grid[p][j]);
            }
            for (int i = p; i < m - p - 1; ++i) {
                nums.push_back(grid[i][n - p - 1]);
            }
            for (int j = n - p - 1; j > p; --j) {
                nums.push_back(grid[m - p - 1][j]);
            }
            for (int i = m - p - 1; i > p; --i) {
                nums.push_back(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[k++ % l];
            }
            for (int i = p; i < m - p - 1; ++i) {
                grid[i][n - p - 1] = nums[k++ % l];
            }
            for (int j = n - p - 1; j > p; --j) {
                grid[m - p - 1][j] = nums[k++ % l];
            }
            for (int i = m - p - 1; i > p; --i) {
                grid[i][p] = nums[k++ % l];
            }
        };
        for (int p = 0; p < min(m, n) / 2; ++p) {
            rotate(p, k);
        }
        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
34
35
36
37
38
39
40
41
42
43
44
45
func rotateGrid(grid [][]int, k int) [][]int {
    m, n := len(grid), len(grid[0])

    rotate := func(p, k int) {
        nums := []int{}
        for j := p; j < n-p-1; j++ {
            nums = append(nums, grid[p][j])
        }
        for i := p; i < m-p-1; i++ {
            nums = append(nums, grid[i][n-p-1])
        }
        for j := n - p - 1; j > p; j-- {
            nums = append(nums, grid[m-p-1][j])
        }
        for i := m - p - 1; i > p; i-- {
            nums = append(nums, grid[i][p])
        }
        l := len(nums)
        k %= l
        if k == 0 {
            return
        }
        for j := p; j < n-p-1; j++ {
            grid[p][j] = nums[k]
            k = (k + 1) % l
        }
        for i := p; i < m-p-1; i++ {
            grid[i][n-p-1] = nums[k]
            k = (k + 1) % l
        }
        for j := n - p - 1; j > p; j-- {
            grid[m-p-1][j] = nums[k]
            k = (k + 1) % l
        }
        for i := m - p - 1; i > p; i-- {
            grid[i][p] = nums[k]
            k = (k + 1) % l
        }
    }

    for i := 0; i < m/2 && i < n/2; i++ {
        rotate(i, k)
    }
    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
34
35
36
37
38
39
40
function rotateGrid(grid: number[][], k: number): number[][] {
    const m = grid.length;
    const n = grid[0].length;
    const rotate = (p: number, k: number) => {
        const nums: number[] = [];
        for (let j = p; j < n - p - 1; ++j) {
            nums.push(grid[p][j]);
        }
        for (let i = p; i < m - p - 1; ++i) {
            nums.push(grid[i][n - p - 1]);
        }
        for (let j = n - p - 1; j > p; --j) {
            nums.push(grid[m - p - 1][j]);
        }
        for (let i = m - p - 1; i > p; --i) {
            nums.push(grid[i][p]);
        }
        const l = nums.length;
        k %= l;
        if (k === 0) {
            return;
        }
        for (let j = p; j < n - p - 1; ++j) {
            grid[p][j] = nums[k++ % l];
        }
        for (let i = p; i < m - p - 1; ++i) {
            grid[i][n - p - 1] = nums[k++ % l];
        }
        for (let j = n - p - 1; j > p; --j) {
            grid[m - p - 1][j] = nums[k++ % l];
        }
        for (let i = m - p - 1; i > p; --i) {
            grid[i][p] = nums[k++ % l];
        }
    };
    for (let p = 0; p < Math.min(m, n) >> 1; ++p) {
        rotate(p, k);
    }
    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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
impl Solution {
    pub fn rotate_grid(grid: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
        let mut grid = grid;
        let m = grid.len();
        let n = grid[0].len();

        let mut rotate = |p: usize, mut k: usize| {
            let mut nums = Vec::new();
            for j in p..n - p - 1 {
                nums.push(grid[p][j]);
            }
            for i in p..m - p - 1 {
                nums.push(grid[i][n - p - 1]);
            }
            for j in (p + 1..n - p).rev() {
                nums.push(grid[m - p - 1][j]);
            }
            for i in (p + 1..m - p).rev() {
                nums.push(grid[i][p]);
            }
            let l = nums.len();
            if l == 0 {
                return;
            }
            k %= l;
            if k == 0 {
                return;
            }
            for j in p..n - p - 1 {
                grid[p][j] = nums[k];
                k = (k + 1) % l;
            }
            for i in p..m - p - 1 {
                grid[i][n - p - 1] = nums[k];
                k = (k + 1) % l;
            }
            for j in (p + 1..n - p).rev() {
                grid[m - p - 1][j] = nums[k];
                k = (k + 1) % l;
            }
            for i in (p + 1..m - p).rev() {
                grid[i][p] = nums[k];
                k = (k + 1) % l;
            }
        };

        let layers = std::cmp::min(m / 2, n / 2);
        for i in 0..layers {
            rotate(i, k as usize);
        }
        grid
    }
}

Comments