# Shift 2D Grid
**Difficulty:** EASY
[External](https://leetcode.com/problems/shift-2d-grid)
Canonical: https://scaleengineer.com/dsa/problems/shift-2d-grid
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/shift-2d-grid/image0.png) 

**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:**

![](https://assets.glich.co/dsa/shift-2d-grid/image1.png) 

**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`

# Approaches
## Simulation of k Shifts
This approach directly simulates the shifting process as described in the problem. It iterates `k` times, and in each iteration, it calculates the new position of every element after one shift and stores it in a temporary grid. After all elements are moved, the temporary grid's contents are copied back to the original grid for the next iteration.
**Time:** O(k * m * n). For each of the `k` shifts, we iterate over all `m * n` elements. · **Space:** O(m * n). A temporary grid of size `m * n` is created in each of the `k` iterations.
**Pros:** Simple to understand and implement as it directly follows the problem description.
**Cons:** Highly inefficient for large values of `k`, as the entire grid is processed `k` times.; Creates a new grid in every iteration, leading to high memory churn.
### Explanation
The algorithm performs the shift operation `k` times. For each of the `k` steps, a new `m x n` grid, `newGrid`, is created to store the state after one shift. We iterate through each cell `(i, j)` of the current `grid`. The value `grid[i][j]` is placed into its new position in `newGrid` based on the shift rules. After iterating through all cells, the `grid` is updated with the contents of `newGrid`. This process is repeated `k` times. Finally, the grid is converted to the required list format.

```java
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;

        for (int shift = 0; shift < k; shift++) {
            int[][] newGrid = new int[m][n];
            
            // Case 1: Element at grid[i][j] moves to grid[i][j + 1]
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n - 1; j++) {
                    newGrid[i][j + 1] = grid[i][j];
                }
            }
            
            // Case 2: Element at grid[i][n - 1] moves to grid[i + 1][0]
            for (int i = 0; i < m - 1; i++) {
                newGrid[i + 1][0] = grid[i][n - 1];
            }
            
            // Case 3: Element at grid[m - 1][n - 1] moves to grid[0][0]
            newGrid[0][0] = grid[m - 1][n - 1];
            
            grid = newGrid;
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int[] row : grid) {
            List<Integer> listRow = new ArrayList<>();
            for (int cell : row) {
                listRow.add(cell);
            }
            result.add(listRow);
        }
        return result;
    }
}
```
### Algorithm
1. Loop `k` times to simulate each shift.
2. In each iteration, create a new temporary grid `tempGrid` of size `m x n`.
3. Iterate through each cell `(i, j)` of the input `grid`.
4. Calculate the new position `(newI, newJ)` after one single shift:
   - If `j < n - 1`, the element moves to `(i, j + 1)`.
   - If `j == n - 1` and `i < m - 1`, the element moves to `(i + 1, 0)`.
   - If `i == m - 1` and `j == n - 1`, the element moves to `(0, 0)`.
5. Place the element `grid[i][j]` into `tempGrid` at the calculated new position.
6. After iterating through all cells, replace the original `grid` with `tempGrid`.
7. After `k` iterations, convert the final `grid` into a `List<List<Integer>>` and return it.

## Flatten to 1D, Shift, and Reconstruct
This approach recognizes that the 2D grid shift is equivalent to a 1D circular array rotation. The grid is first flattened into a 1D array. Then, a circular shift of `k` positions is applied to this 1D array. Finally, the shifted 1D array is converted back into an `m x n` grid.
**Time:** O(m * n). We iterate through the grid elements to flatten, perform the rotation (which is also O(m*n)), and then reconstruct the grid. · **Space:** O(m * n). We use an auxiliary 1D list of size `m * n`.
**Pros:** Much more efficient than simulation for large `k` as its complexity is independent of `k`.; Conceptually clean by reducing a 2D problem to a 1D one.
**Cons:** Requires extra space proportional to the size of the grid for the intermediate 1D list.; Involves multiple passes over the data: one to flatten, one to shift, and one to reconstruct.
### Explanation
The core idea is to simplify the 2D shift into a 1D rotation. First, we calculate the total number of elements, `total = m * n`. Since shifting `total` times brings the grid back to its original state, we only need to consider the effective number of shifts, `k % total`. We create a temporary 1D array and populate it with the elements of the grid. Then, we create a new 1D array for the shifted elements. The element at index `p` in the flattened array moves to the new index `(p + k) % total`. Finally, we construct the result 2D grid from this shifted 1D array.

```java
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int total = m * n;
        k = k % total;

        List<Integer> flatList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                flatList.add(grid[i][j]);
            }
        }

        // Reverse the entire list
        Collections.reverse(flatList);
        // Reverse the first k elements
        Collections.reverse(flatList.subList(0, k));
        // Reverse the remaining elements
        Collections.reverse(flatList.subList(k, total));

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add(flatList.get(i * n + j));
            }
            result.add(row);
        }
        
        return result;
    }
}
```
### Algorithm
1. Get grid dimensions `m` and `n`. Calculate total elements `total = m * n`.
2. Flatten the 2D `grid` into a 1D array or list, say `flatList`.
3. The shift operation on the 2D grid is equivalent to a right circular shift on the 1D list. The number of effective shifts is `k % total`.
4. Create a new 1D list, `rotatedList`, to store the result of the shift.
5. Populate `rotatedList` by taking the last `k % total` elements of `flatList` followed by the first `total - (k % total)` elements.
6. Create a new `m x n` result grid.
7. Reconstruct the 2D grid by populating it with elements from `rotatedList`. The element at `rotatedList[p]` goes to `result[p / n][p % n]`.
8. Return the result grid.

## Direct Calculation using Modulo Arithmetic
This is the most efficient approach. Instead of simulating or using intermediate data structures, we directly compute the final grid. For each cell `(i, j)` in the original grid, we calculate where it will end up after `k` shifts. This is done by converting the 2D coordinates to a 1D index, applying the shift arithmetically, and converting the result back to 2D coordinates for the new grid.
**Time:** O(m * n). We iterate through the grid once to compute the new grid. The modulo and division operations are constant time. · **Space:** O(m * n). This space is used for the result grid, which is required by the problem's return type. The auxiliary space besides the output is O(1).
**Pros:** Most efficient time complexity, O(m * n), independent of `k`.; Single-pass solution over the grid elements.; Avoids creating large intermediate data structures beyond the required result grid.
**Cons:** Requires space for the new grid, although this is generally required for the return type anyway.
### Explanation
The key insight is that we can determine the final position of any element with a simple formula. We create a new result grid and iterate through each cell `(i, j)` of the original grid. For each element, we map its 2D coordinates `(i, j)` to a 1D index `p = i * n + j`. After `k` shifts, its new 1D index will be `p_new = (p + k) % (m * n)`. We then convert this new 1D index back to 2D coordinates `(new_i, new_j)` and place the element `grid[i][j]` at `result[new_i][new_j]`. This process fills the new grid in a single pass over the original grid.

```java
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int total = m * n;
        
        // The result format is List<List<Integer>>, so we create it upfront.
        // Initialize with placeholder values.
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add(0);
            }
            result.add(row);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int oldIndex1D = i * n + j;
                int newIndex1D = (oldIndex1D + k) % total;
                int newI = newIndex1D / n;
                int newJ = newIndex1D % n;
                result.get(newI).set(newJ, grid[i][j]);
            }
        }
        
        return result;
    }
}
```
### Algorithm
1. Get grid dimensions `m` and `n`. Calculate total elements `total = m * n`.
2. Create a new result grid `resultGrid` of size `m x n`.
3. Iterate through each cell `(i, j)` of the original `grid`.
4. For each element `grid[i][j]`, calculate its 1D index: `oldIndex1D = i * n + j`.
5. Calculate its new 1D index after `k` shifts: `newIndex1D = (oldIndex1D + k) % total`.
6. Convert the `newIndex1D` back to 2D coordinates: `newI = newIndex1D / n`, `newJ = newIndex1D % n`.
7. Place the element in the new grid: `resultGrid[newI][newJ] = grid[i][j]`.
8. After iterating through all elements, convert `resultGrid` to the required `List<List<Integer>>` format and return it.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> shiftGrid(int[][] grid, int k) {
    int m = grid.length, n = grid[0].length;
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < m; ++i) {
      List<Integer> row = new ArrayList<>();
      for (int j = 0; j < n; ++j) {
        row.add(0);
      }
      ans.add(row);
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int idx = (i * n + j + k) % (m * n);
        int x = idx / n, y = idx % n;
        ans.get(x).set(y, grid[i][j]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> shiftGrid(vector<vector<int>> &grid, int k) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int idx = (i * n + j + k) % (m * n);
        int x = idx / n, y = idx % n;
        ans[x][y] = grid[i][j];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]: m, n = len(grid), len(grid[0]) ans = [[0] * n for _ in range(m)] for i, row in enumerate(grid): for j, v in enumerate(row): x, y = divmod((i * n + j + k) % (m * n), n) ans[x][y] = v return ans

```