Given a 2D grid of size m x n&nbsp;and an integer k. You need to shift the grid&nbsp;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&nbsp;- 1][n - 1] moves to grid[0][0].


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

&nbsp;
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]]


&nbsp;
Constraints:


	m ==&nbsp;grid.length
	n ==&nbsp;grid[i].length
	1 &lt;= m &lt;= 50
	1 &lt;= n &lt;= 50
	-1000 &lt;= grid[i][j] &lt;= 1000
	0 &lt;= k &lt;= 100


class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        cache = []
        for i in range(m):
            for j in range(n):
                cache.append(grid[i][j])
        
        k %= len(cache)
        new_vals = cache[-k:] + cache[:-k]
        
        cur = 0
        for i in range(m):
            for j in range(n):
                grid[i][j] = new_vals[cur]
                cur += 1
        
        return grid
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        // just bruteforce??? O(i*j*k)
        // instead we calculate the final position at once!
        
        int m = grid.length;  // row
        int n = grid[0].length;  // column
        
        int[][] arr = new int[m][n];
        
        // Since moving m*n times will result in same matrix, we do this:
        k = k % (m*n);
        
        // Then we move each element
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // for calculating column, it back to the original position
                // every n steps
                int column = (j + k) % n;
                
                // for calculating row, we move to the next row each time
                // it exceed the last element on the current row.
                // For example when 2 moves k=5 steps it turns to the (+2) row.
                // Thus it's original row + ((original column + steps) / n)
                // But if 2 moves k=8 steps it turns to the (0,0),
                // and row + ((original column + steps) / n) gives 0+(9/3)=3 (out of bounds)
                // so we'll need to % number of rows to get 0. (circle back)
                int row = (i + ((j + k) / n)) % m;
                arr[row][column] = grid[i][j];
            }
        }
        return (List) Arrays.asList(arr);
    }
}
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        
        deque<int>dq;
        
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                dq.push_back(grid[i][j]);
            }
        }
        
        int last = dq.size()-1;
        while(k--){
            int a = dq[last];
            dq.push_front(a);
            dq.pop_back();
        }
        
        int p = 0;
        
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                grid[i][j] = dq[p];
                p++;
            }
        }
        
        return grid;
    }
};
/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number[][]}
 */
var shiftGrid = function(grid, k) {

    let m = grid.length
    let n = grid[0].length

    for (let r = 0; r < k; r++) {
        const newGrid = Array(m).fill("X").map(() => Array(n).fill("X"))
        for (let i = 0; i < m; i++) {
            for (let j = 1; j < n; j++) {
                newGrid[i][j] = grid[i][j-1]
            }
         }

        for (let i = 1; i < m; i++) {
            newGrid[i][0] = grid[i-1][n-1]
        }

        newGrid[0][0] = grid[m-1][n-1]

        //copy the new grid for the next iteration
        grid = newGrid
    }

    return grid

};
Shift 2D Grid