Problem Explanation

You are given a 2D grid (a matrix) with m rows and n columns. You are also given an integer k that represents the number of shift operation you have to perform on the grid.

A single shift operation works as follow:

• The element at the i-th row and j-th column (grid[i][j]) is moved to the j+1-th column of the i-th row (grid[i][j+1]).
• The element at the last column of the i-th row (grid[i][n-1]) is moved to the first column of the (i+1)-th row (grid[i+1][0]).
• The element at the last column of the last row (grid[n-1][n-1]) is moved to the first column of the first row (grid[0][0]).

You have to return the grid after applying the shift operation k times.

Let's walk through an example:

Given grid = [[1,2,3],[4,5,6],[7,8,9]] and k = 1.

After shifting:

• 1 shifts to the position of 2;
• 2 shifts to the position of 3;
• 3 shifts to the position of 4;
• 9 shifts to the position of 1.

Therefore, after one shift, the new grid becomes [[9,1,2],[3,4,5],[6,7,8]].

Approach

• To simulate a single shift operation, we need to shift every element grid[i][j] to the position grid[i][j+1].
• If j+1 is out of the grid, we need to adjust it to the position grid[i+1][0].
• If i+1 is out of the grid, we need to adjust it to the position grid[0][0].
• Since we have mn elements and k shift operations, we can reduce the total number of shift operations by taking the modulo of mn and k.

Algorithms and Data Structures

This problem can be solved by using a basic simulation approach where we move every element to its new position according to the shift operation rules. We use arrays to store the grid and its updated version after performing the shifts.

Python

1
2python
3class Solution:
4    def shiftGrid(self, grid, k):
5        m, n = len(grid), len(grid[0])
6        k %= m * n  # reduce k
7        res = [[0] * n for _ in range(m)]
8        for i in range(m):
9            for j in range(n):
10                idx = (i * n + j + k) % (m * n)
11                new_i, new_j = divmod(idx, n)
12                res[new_i][new_j] = grid[i][j]
13        return res

Java

1
2java
3class Solution {
4    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
5        int m = grid.length, n = grid[0].length;
6        k %= m * n;
7        int[][] result = new int[m][n];
8        for (int i = 0; i < m; i++) {
9            for (int j = 0; j < n; j++) {
10                int idx = (i * n + j + k) % (m * n);
11                result[idx / n][idx % n] = grid[i][j];
12            }
13        }
14        List<List<Integer>> list = new ArrayList<>();
15        for (int[] row : result) {
16            List<Integer> subList = new ArrayList<>();
17            for (int num : row) {
18                subList.add(num);
19            }
20            list.add(subList);
21        }
22        return list;
23    }
24}

JavaScript

1
2javascript
3var shiftGrid = function(grid, k) {
4    const m = grid.length;
5    const n = grid[0].length;
6    const newGrid = Array(m).fill().map(() => Array(n).fill(0));
7    k %= m * n;
8
9    for(let i=0; i<m; i++) {
10        for(let j=0; j<n; j++) {
11            const index = ((i*n)+j+k) % (m*n);
12            const x = Math.floor(index/n);
13            const y = index % n;
14            newGrid[x][y] = grid[i][j];
15        }
16    }
17    return newGrid;
18};

C++

1
2c++
3class Solution {
4public:
5    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
6        int m = grid.size(), n = grid[0].size();
7        k %= m * n;
8        vector<vector<int>> result(m, vector<int>(n));
9        for (int i = 0; i < m; i++) {
10            for (int j = 0; j < n; j++) {
11                int index = (i * n + j + k) % (m * n);
12                result[index / n][index % n] = grid[i][j];
13            }
14        }
15        return result;
16    }
17};

C#

1
2csharp
3public class Solution {
4    public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
5        int rows = grid.Length;
6        int cols = grid[0].Length;
7        k %= (rows * cols);
8        int[][] result = new int[rows][];
9        for (int row = 0; row < rows; row++) {
10            result[row] = new int[cols];
11            for (int col = 0; col < cols; col++) {
12                int linearIndex = ((row * cols) + col + k) % (rows * cols);
13                int newRow = linearIndex / cols;
14                int newCol = linearIndex % cols;
15                result[newRow][newCol] = grid[row][col];
16            }
17        }
18        return result;
19    }
20}

Time and Space Complexity

The time complexity for this problem is O(m*n). Since in the worst-case scenario, we iterate over all the elements in the grid once, where m is the number of rows and n is the number of columns in the grid.

The space complexity is also O(m*n). We are creating a new grid to store the shifted elements, which take up as much space as the original grid.

Final Thoughts

As we have seen, this problem is pretty straight forward if we understand the question requirements. Some people might be confused about whether to move the elements physically in-place inside the input grid array or to create a new grid.

However, as per the problem's requirements and constraints, creating a new grid seems to be the most logical approach. Besides, this solution works well without mutating the original input grid array, which is a pretty good practice in terms of functional programming.

Also, the problem is not about optimizing or finding more efficient solutions, but it is about understanding an algorithm's steps and its application on arrays or 2D grids, the practical coding skill being tested here is the skill to translate a real world situation into code. This is a common theme in technical interviews, where the task is often to translate a complex problem into an algorithm that a machine can understand.

We hope that having walked through this problem, and seen examples in Python, Javascript, Java, C++ and C#, you now feel more comfortable about tackling similar problems in your future coding journey.