Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1914.html

1914. Cyclically Rotating a Grid

Level

Medium

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:

Image text

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:

Image text

Return the matrix after applying k cyclic rotations to it.

Example 1:

Image text

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:

Image text

Image text

Image text

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 <= 10^9

Solution

First, get the spiral order of all the elements in grid. Next, split the elements into different layers, rotate the elements in each layer, and update the rotated spiral order. Finally, put the elements in the rotated spiral order into the grid.

To split the elements into different layers, the first layer has (m + n - 2) * 2 elements, and for the remaining layers, the number of elements in each layer will be subtracted by 8. When there are no remaining elements in the spiral order, all elements are visited.

  • class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        List<Integer> order = spiralOrder(grid);
        List<Integer> rotatedOrder = new ArrayList<Integer>();
        int startIndex = 0;
        int layerSize = (m + n - 2) * 2;
        int total = m * n;
        while (startIndex < total) {
            List<Integer> layer = order.subList(startIndex, startIndex + layerSize);
            int curIndex = k % layerSize;
            for (int i = 0; i < layerSize; i++) {
                rotatedOrder.add(layer.get(curIndex));
                curIndex = (curIndex + 1) % layerSize;
            }
            startIndex += layerSize;
            layerSize -= 8;
        }
        return generateGrid(m, n, rotatedOrder);
    }

    public List<Integer> spiralOrder(int[][] grid) {
        List<Integer> order = new ArrayList<Integer>();
        int m = grid.length, n = grid[0].length;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++)
                order.add(grid[top][column]);
            for (int row = top + 1; row <= bottom; row++)
                order.add(grid[row][right]);
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--)
                    order.add(grid[bottom][column]);
                for (int row = bottom; row > top; row--)
                    order.add(grid[row][left]);
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }

    public int[][] generateGrid(int m, int n, List<Integer> order) {
        int[][] grid = new int[m][n];
        int row = 0, column = 0;
        int[][] directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
        int directionIndex = 0;
        int size = order.size();
        for (int i = 0; i < size; i++) {
            grid[row][column] = order.get(i);
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= m || nextColumn < 0 || nextColumn >= n || grid[nextRow][nextColumn] != 0)
                directionIndex = (directionIndex + 1) % 4;
            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }
        return grid;
    }
}

############

class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int s1 = 0, e1 = 0;
        int s2 = m - 1, e2 = n - 1;
        while (s1 <= s2 && e1 <= e2) {
            rotate(grid, s1++, e1++, s2--, e2--, k);
        }
        return grid;
    }

    private void rotate(int[][] grid, int s1, int e1, int s2, int e2, int k) {
        List<Integer> t = new ArrayList<>();
        for (int j = e2; j > e1; --j) {
            t.add(grid[s1][j]);
        }
        for (int i = s1; i < s2; ++i) {
            t.add(grid[i][e1]);
        }
        for (int j = e1; j < e2; ++j) {
            t.add(grid[s2][j]);
        }
        for (int i = s2; i > s1; --i) {
            t.add(grid[i][e2]);
        }
        int n = t.size();
        k %= n;
        if (k == 0) {
            return;
        }
        k = n - k;
        for (int j = e2; j > e1; --j) {
            grid[s1][j] = t.get(k);
            k = (k + 1) % n;
        }
        for (int i = s1; i < s2; ++i) {
            grid[i][e1] = t.get(k);
            k = (k + 1) % n;
        }
        for (int j = e1; j < e2; ++j) {
            grid[s2][j] = t.get(k);
            k = (k + 1) % n;
        }
        for (int i = s2; i > s1; --i) {
            grid[i][e2] = t.get(k);
            k = (k + 1) % n;
        }
    }
}

  • // OJ: https://leetcode.com/problems/cyclically-rotating-a-grid/
// Time: O(MN)
// Space: O(M + N)
class Solution {
    void rotate(vector<int>& A, int k) {
        int cnt = 0, N = A.size();
        k %= N;
        if (k == 0) return;
        for (int i = 0; cnt < N; ++i) {
            int j = i, tmp = A[j];
            do {
                int t = (j + k) % N, next = A[t];
                A[t] = tmp;
                tmp = next;
                j = t;
                ++cnt;
            } while (j != i);
        }
    }
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& A, int K) {
        int M = A.size(), N = A[0].size();
        for (int i = 0; i < min(M, N) / 2; ++i) {
            int x = i, y = i, h = M - 2 * i, w = N - 2 * i, k = 0, len = 2 * (h + w - 2);
            vector<int> v(len);
            for (int j = 1; j < w; ++j, ++y) v[k++] = A[x][y];
            for (int j = 1; j < h; ++j, ++x) v[k++] = A[x][y];
            for (int j = 1; j < w; ++j, --y) v[k++] = A[x][y];
            for (int j = 1; j < h; ++j, --x) v[k++] = A[x][y];
            rotate(v, len - K % len);
            x = i, y = i, k = 0;
            for (int j = 1; j < w; ++j, ++y) A[x][y] = v[k++];
            for (int j = 1; j < h; ++j, ++x) A[x][y] = v[k++];
            for (int j = 1; j < w; ++j, --y) A[x][y] = v[k++];
            for (int j = 1; j < h; ++j, --x) A[x][y] = v[k++] ;
        }
        return A;
    }
};

  • class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        def rotate(grid, s1, e1, s2, e2, k):
            t = []
            for j in range(e2, e1, -1):
                t.append(grid[s1][j])
            for i in range(s1, s2):
                t.append(grid[i][e1])
            for j in range(e1, e2):
                t.append(grid[s2][j])
            for i in range(s2, s1, -1):
                t.append(grid[i][e2])
            k %= len(t)
            t = t[-k:] + t[:-k]
            k = 0
            for j in range(e2, e1, -1):
                grid[s1][j] = t[k]
                k += 1
            for i in range(s1, s2):
                grid[i][e1] = t[k]
                k += 1
            for j in range(e1, e2):
                grid[s2][j] = t[k]
                k += 1
            for i in range(s2, s1, -1):
                grid[i][e2] = t[k]
                k += 1

        m, n = len(grid), len(grid[0])
        s1 = e1 = 0
        s2, e2 = m - 1, n - 1
        while s1 <= s2 and e1 <= e2:
            rotate(grid, s1, e1, s2, e2, k)
            s1 += 1
            e1 += 1
            s2 -= 1
            e2 -= 1
        return grid

############

# 1914. Cyclically Rotating a Grid
# https://leetcode.com/problems/cyclically-rotating-a-grid

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        rows, cols = len(grid), len(grid[0])
        
        for r in range(min(rows, cols) // 2):
            i = j = r
            vals = []
            
            for jj in range(j, cols - j - 1):
                vals.append(grid[i][jj])
            
            for ii in range(i, rows - i - 1):
                vals.append(grid[ii][cols - j - 1])
            
            for jj in range(cols - j - 1, j, -1):
                vals.append(grid[rows - i - 1][jj])
            
            for ii in range(rows - i - 1, i, -1):
                vals.append(grid[ii][j])
            
            kk = k % len(vals)
            vals = vals[kk:] + vals[:kk]
            x = 0
            
            for jj in range(j, cols - j - 1):
                grid[i][jj] = vals[x]; x += 1
            
            for ii in range(i, rows - i - 1):
                grid[ii][cols - j - 1] = vals[x]; x += 1
            
            for jj in range(cols - j - 1, j, -1):
                grid[rows - i - 1][jj] = vals[x]; x += 1
            
            for ii in range(rows - i - 1, i, -1):
                grid[ii][j] = vals[x]; x += 1
        
        return grid
            


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

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

All Problems

All Solutions