Problem Statement in English

You’re 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, the following happens:

  • 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 k shift operations.

Approach

We can flatten the 2D grid into a 1D array, perform the shift operation on the 1D array, and then reshape it back into a 2D grid. The shift operation can be efficiently performed using array rotation techniques.

We mod k by the total number of elements in the grid to avoid unnecessary full rotations.

The actual shifting can be done by reversing parts of the array to achieve the desired rotation.

And we’re done!

Solution in Python


class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        M = len(grid)
        N = len(grid[0])
        total = M * N

        k %= total

        arr = []

        def rotate(n):
            reverse(0, n - 1)
            reverse(0, k - 1)
            reverse(k, n - 1)

        def reverse(start, end):
            while start < end:
                arr[start], arr[end] = arr[end], arr[start]
                start += 1
                end -= 1

        for i in range(M):
            for j in range(N):
                arr.append(grid[i][j])

        rotate(total)

        for i in range(M):
            for j in range(N):
                grid[i][j] = arr[i*N+j]

        return grid

Complexity

  • Time: $O(M \times N)$
    Since we are iterating through the entire grid to flatten it into a 1D array and then performing the rotation, the time complexity is linear with respect to the number of elements in the grid.

  • Space: $O(M \times N)$
    Since we are using an additional array to store the flattened grid, the space complexity is also linear with respect to the number of elements in the grid.

And we are done.