1260. Shift 2D Grid

Problem

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

https://leetcode.com/problems/shift-2d-grid/

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Test Cases

1 2	class Solution: def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:

solution_test.py

import copy
import pytest

from solution import Solution


@pytest.mark.parametrize('grid, k, expected', [
    ([[1,2,3],[4,5,6],[7,8,9]], 1, [[9,1,2],[3,4,5],[6,7,8]]),
    ([[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], 4, [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]),
    ([[1,2,3],[4,5,6],[7,8,9]], 9, [[1,2,3],[4,5,6],[7,8,9]]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, grid, k, expected):
    assert sol.shiftGrid(copy.deepcopy(grid), k) == expected

Thoughts

In-place 轮换比较麻烦，一般的实现方式也是需要用 O(m * n) 的辅助空间。直接生成新的二维数组写入轮换后的结果即可。

Code

solution.py

class Solution:
    def shiftGrid(self, grid: list[list[int]], k: int) -> list[list[int]]:
        m = len(grid)
        n = len(grid[0])
        mn = m * n
        k %= mn
        if k == 0: return grid

        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r, c = divmod(k, n)
                res[r][c] = grid[i][j]
                k = (k + 1) % mn

        return res

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。