Description
https://leetcode.com/problems/shift-2d-grid/
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 togrid[i][j + 1]. - Element at
grid[i][n - 1]moves togrid[i + 1][0]. - Element at
grid[m - 1][n - 1]moves togrid[0][0].
Return the 2D grid after applying shift operation k times.
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.lengthn == grid[i].length1 <= m <= 501 <= n <= 50-1000 <= grid[i][j] <= 10000 <= k <= 100
Explanation
Implement simulation to perform the transformation the problem describes.
Python Solution
class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
for _ in range(k):
for i in range(0, len(grid)):
last_column = None
for j in range(len(grid[0]) - 1, -1, -1):
if j == len(grid[0]) - 1:
last_column = grid[i][j]
else:
grid[i][j + 1] = grid[i][j]
if j == 0:
grid[i][j] = last_column
last_row = None
for i in range(len(grid) - 1, -1, -1):
if i == len(grid) - 1:
last_row = grid[i][0]
else:
grid[i + 1][0] = grid[i][0]
if i == 0:
grid[i][0] = last_row
return grid- Time Complexity: O(kMN).
- Space Complexity: O(MN).