1
class Solution {
2
  public List<List<Integer>> shiftGrid(int[][] grid, int k) {
3
    // just bruteforce??? O(i*j*k)
4
    // instead we calculate the final position at once!
5

6
    int m = grid.length; // row
7
    int n = grid[0].length; // column
8

9
    int[][] arr = new int[m][n];
10

11
    // Since moving m*n times will result in same matrix, we do this:
12
    k = k % (m * n);
13

14
    // Then we move each element
15
    for (int i = 0; i < m; i++) {
16
      for (int j = 0; j < n; j++) {
17
        // for calculating column, it back to the original position
18
        // every n steps
19
        int column = (j + k) % n;
20

21
        // for calculating row, we move to the next row each time
22
        // it exceed the last element on the current row.
23
        // For example when 2 moves k=5 steps it turns to the (+2) row.
24
        // Thus it's original row + ((original column + steps) / n)
25
        // But if 2 moves k=8 steps it turns to the (0,0),
26
        // and row + ((original column + steps) / n) gives 0+(9/3)=3 (out of bounds)
27
        // so we'll need to % number of rows to get 0. (circle back)
28
        int row = (i + ((j + k) / n)) % m;
29
        arr[row][column] = grid[i][j];
30
      }
31
    }
32
    return (List) Arrays.asList(arr);
33
  }
34
}