subject

1260. Two dimensional grid migration

To give you one m That's ok n Two dimensional grid of columns grid And an integer k. You need to grid transfer k Time .

Every time 「 transfer 」 The operation will trigger the following activities ：

• be located grid[i][j] The element will be moved to grid[i][j + 1].
• be located grid[i][n - 1] The element will be moved to grid[i + 1][0].
• be located grid[m - 1][n - 1] The element will be moved to grid[0][0].

Please return k The final result after the migration operation Two dimensional meshes .

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]]

Tips ：

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

Ideas

• Observe the movement , It is not difficult to find the law of movement, which is equivalent to each number moving forward after horizontal expansion k A unit of

Code

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m,n = len(grid), len(grid[0])
        ret = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                newIndex = (i*n+j+k) % (m*n)
                ret[newIndex//n][newIndex%n] = grid[i][j]
        return ret

Complexity

• Time complexity ：$O(mn)$
• Spatial complexity ：$O(1)$