#
# Create by Hua on 4/17/22.
#

"""
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.



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


"""


class Solution(object):
    def shiftGrid(self, grid, k):
        """
        :type grid: List[List[int]]
        :type k: int
        :rtype: List[List[int]]

        thought: convert 2d to 1d, and rotate k times and put back in 2d
        123456789
        912345678
        04/17/2022 11:45	Accepted	130 ms	13.9 MB	python
        easy 10-20 min.
        """
        m = len(grid)
        n = len(grid[0])
        # flat 2d to 1d
        a = list()
        for i in range(m):
            a.extend(grid[i])

        k = k % (m*n)
        b = a[m*n-k:] + a[:m*n-k]
        for i in range(m):
            for j in range(n):
                grid[i][j] = b.pop(0)
        return grid